Submission #772327

#TimeUsernameProblemLanguageResultExecution timeMemory
772327SLin25Hacker (BOI15_hac)C++14
20 / 100
38 ms8272 KiB
#include <bits/stdc++.h> #include <iostream> using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int arr[n]; int pref[n+1]{}; int k = (n + 1) / 2; for (int i = 0; i < n; i++) { cin >> arr[i]; } for (int i = 1; i <= n; i++) { pref[i] += pref[i-1] + arr[i-1]; } int val[n]; //segment ending at index for (int i = 0; i < n; i++) { int prev = i - k + 1; int tmp = 0; if (prev < 0) { tmp = pref[i+1] + pref[n] - pref[n + prev]; } else { tmp = pref[i+1] - pref[prev]; } val[i] = tmp; } deque<pair<int, int>> q; int ans = 0; for (int i = 0; i < k; i++) { while (!q.empty() && q.back().first > val[i]) { q.pop_back(); } q.push_back({val[i], i}); } ans = max(ans, q.front().first); for (int i = k; i < n; i++) { while (!q.empty() && q.back().first > val[i]) { q.pop_back(); } q.push_back({val[i], i}); if (q.front().second == i - k) q.pop_front(); ans = max(ans, q.front().first); } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...