# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
633179 | 2022-08-21T18:52:47 Z | Alma | Hacker (BOI15_hac) | C++17 | 1 ms | 212 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second using ll = long long; using ii = pair<int,int>; const int INF = 1e9; const ll LLINF = 1e18; using vi = vector<int>; using vvi = vector<vi>; void setIO (string fileName) { ios::sync_with_stdio(false); cin.tie(NULL); if (fileName != "std") { freopen((fileName + ".in").c_str(), "r", stdin); freopen((fileName + ".out").c_str(), "w", stdout); } } ll ask (int l, int r, vector<ll>& p) { return p[r] - p[l-1]; } int main() { setIO("std"); int n; cin >> n; vector<ll> a(3*n), p(3*n), seg(n); vi l(n), r(n); for (int i = 0; i < n; i++) { cin >> a[i]; a[n+i] = a[2*n+i] = a[i]; } p[0] = a[0]; for (int i = 1; i < 3*n; i++) { p[i] = p[i-1] + a[i]; } int d = n/2; for (int i = 0; i < n; i++) { int l1 = n+i-d+1, l2 = n+i; int r1 = n+i, r2 = n+i+d-1; int res = 0; for (int cnt = 0; cnt < 30; cnt++) { int x1 = ask(l1, r1, p); int x2 = ask(l2, r2, p); if (x1 > x2) { l2 = (l1+l2) / 2; r2 = (r1+r2) / 2; } else { l1 = (l1+l2) / 2; r1 = (r1+r2) / 2; } res = max(res, max(x2, x2)); } seg[i] = res; l[i] = l1; r[i] = r1; } ll ans = 0, mx = ask(n, 2*n-1, p); for (int i = 0; i < n; i++) { ans = max(ans, mx - seg[(i + n/2) % n]); if (n % 2 == 1) ans = max(ans, mx - seg[(i + (n+1)/2) % n]); } cout << ans << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |