Submission #995223

#TimeUsernameProblemLanguageResultExecution timeMemory
995223BF001Hacker (BOI15_hac)C++17
100 / 100
284 ms26364 KiB
#include <bits/stdc++.h> using namespace std; #define N 500005 #define int long long int n, a[2 * N], res[N]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i]; res[i] = 1e18; a[i + n] = a[i]; a[i] += a[i - 1]; } for (int i = n + 1; i <= 2 * n; i++){ a[i] += a[i - 1]; } int sz = (n + 1) / 2; multiset<int> st; for (int i = 1; i <= 2 * n; i++){ if (i + sz - 1 <= 2 * n){ st.insert(a[i + sz - 1] - a[i - 1]); } if (i > sz){ st.erase(st.find(a[i - 1] - a[i - 1 - sz])); } int pos = ((i - 1) % n) + 1; res[pos] = min(res[pos], *st.begin()); } int ans = 0; for (auto i = 1; i <= n; i++) ans = max(ans, res[i]); cout << ans; 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...