Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
98395 | CSYZxiaojinyu | 早凉与序列4 | C++ | 运行出错 | 0 | 0 MS | 244 KB | 3553 | 2023-08-14 17:38:13 |
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; long long a[MAXN], f1[MAXN], f2[MAXN]; long long ans = 0; int n, k; long long x; int cnt1, cnt2, cnt3; void shit(int l, int r) { if (l == r) { ans = max(ans, (k > 0) ? (a[l] + x) : a[l]); return; } int mid = l + r >> 1; shit(l, mid), shit(mid + 1, r); long long sum = a[mid], maxx1 = a[mid]; int maxi1 = mid; for (int i = mid - 1; i >= l; --i) { sum += a[i]; if (sum > maxx1) maxx1 = sum, maxi1 = i; } sum = a[mid + 1]; long long maxx2 = sum; int maxi2 = mid + 1; for (int i = mid + 2; i <= r; ++i) { sum += a[i]; if (sum > maxx2) maxx2 = sum, maxi2 = i; } if (maxi2 - maxi1 + 1 >= k) { ans = max(ans, maxx1 + maxx2 + k * x); ++cnt1; return; } sum = a[mid] + x, maxx1 = sum, maxi1 = mid; for (int i = mid - 1, j = 0; i >= l && j < k; --i, ++j) { sum += a[i] + x; if (sum > maxx1) maxx1 = sum, maxi1 = i; } sum = a[mid + 1] + x, maxx2 = sum, maxi2 = mid + 1; for (int i = mid + 2, j = 0; i <= r && j < k; ++i, ++j) { sum += a[i] + x; if (sum > maxx2) maxx2 = sum, maxi2 = i; } if (maxi2 - maxi1 + 1 <= k) { ans = max(ans, maxx1 + maxx2); ++cnt2; return; } ++cnt3; int ll = max(mid - k + 1, l), rr = mid; sum = 0; for (int i = ll; i <= rr; ++i) { sum += a[i] + x; } int nl = -1, nr; while (ll <= mid) { while (a[ll] + x + (ll > 0 ? f1[ll - 1] : 0) - f1[ll] <= 0 && ll <= mid) { sum -= a[ll] + x; ++ll; } long long xxx = sum + (ll > 0 ? f1[ll - 1] : 0) + (rr + 1 < n ? f2[rr + 1] : 0); if (ans < xxx) ans = xxx, nl = ll, nr = rr; while (rr - ll + 1 < k && rr < r) { ++rr; sum += a[rr] + x; long long xxx = sum + (ll > 0 ? f1[ll - 1] : 0) + (rr + 1 < n ? f2[rr + 1] : 0); if (ans < xxx) ans = xxx, nl = ll, nr = rr; } sum -= a[ll] + x; ++ll; } // if (nl > -1) { // while (nl > l && a[nl - 1] > 0) { // --nl; // ans += a[nl]; // } // while (nr < r && a[nr + 1] > 0) { // ++nr; // ans += a[nr]; // } // } // cout << nl << ' ' << nr << ' ' << mid << '\n'; } long long _a[MAXN]; long long _sum[MAXN]; int main() { freopen("T2.in", "r", stdin); freopen("T2.out", "w", stdout); cin >> n >> k >> x; if (n <= 5000) { if (x < 0) { k = n - k; x = -x; } for (long long i = 1; i <= n; ++i) { cin >> _a[i]; _a[i] -= x; _sum[i] = (_sum[i - 1] + _a[i]); } x <<= 1; long long ans = 0; for (int l = 1; l <= n; ++l) { for (int r = l; r <= n; ++r) { ans = max(ans, _sum[r] - _sum[l - 1] + (x * min(k, r - l + 1))); } } cout << ans; return 0; } if (x < 0) { k = n - k; x = -x; } for (int i = 0; i < n; ++i) { cin >> a[i]; a[i] -= x; } long long sum = 0; for (int i = 0; i < n; ++i) { if (sum + a[i] > 0) { sum += a[i]; } else { sum = 0; } f1[i] = sum; cout << f1[i] << ' '; } sum = 0; for (int i = n - 1; i > -1; --i) { if (sum + a[i] > 0) { sum += a[i]; } else { sum = 0; } f2[i] = sum; } cout << '\n'; for (int i = 0; i < n; ++i) { cout << f2[i] << ' '; } cout << '\n'; x <<= 1; shit(0, n - 1); cout << ans; // cout << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3; return 0; }