제출 #465030

#제출 시각아이디문제언어결과실행 시간메모리
465030JovanBHacker (BOI15_hac)C++17
100 / 100
71 ms21512 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 500000; ll pre[3*N+5]; int a[3*N+5]; deque <pair <int, int>> q; void ubaci(pair <int, int> x){ while(!q.empty() && q.back().first >= x.first) q.pop_back(); q.push_back(x); } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n; cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; a[i+n] = a[i+2*n] = a[i]; } for(int i=1; i<=3*n; i++) pre[i] = pre[i-1] + a[i]; int k = (n+1)/2; for(int j=n+1-k+1; j<=n+1; j++) ubaci({pre[j+k-1] - pre[j-1], j}); int res = q.front().first; for(int i=n+2; i<=2*n; i++){ ubaci({pre[i+k-1] - pre[i-1], i}); while(q.front().second < i-k+1) q.pop_front(); res = max(res, q.front().first); } cout << res << "\n"; 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...