Submission #884632

#TimeUsernameProblemLanguageResultExecution timeMemory
884632MisterReaperHacker (BOI15_hac)C++17
100 / 100
261 ms24420 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int INF = 1E9; #define ONLINE_JUDGE void solve() { int n; cin >> n; vector <int> a(2 * n +1); for(int i = 1; i <= n; i++) { cin >> a[i]; a[i + n] = a[i]; } vector <int> pref = a; for(int i = 1; i <= 2 * n; i++) { pref[i] += pref[i -1]; } auto get = [&](int x, int y) -> int { return pref[x] - pref[y -1]; }; vector <int> ans(n, INF); int sz = (n +1) / 2; multiset <int> ms; for(int i = 1; i <= 2 * n; i++) { if(i + sz -1 <= 2 * n) { ms.emplace(get(i + sz -1, i)); } if(i - sz >= 1) { ms.erase(ms.find(get(i -1, i - sz))); } /* cerr << i << ":\n"; for(const int &j : ms) { cerr << j << " "; } cerr << "\n"; */ ans[i % n] = min(ans[i % n], *ms.begin()); } cout << *max_element(ans.begin(), ans.end()); return; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...