제출 #425752

#제출 시각아이디문제언어결과실행 시간메모리
425752egekabasBigger segments (IZhO19_segments)C++14
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; ll n; ll a[500009], pre[500009]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin >> n; for(ll i = 0; i < n; ++i){ cin >> a[i]; pre[i] = a[i]; if(i) pre[i] += pre[i-1]; } pii last = {-1e9, 0}; ll befsum = 0, cursum = a[0]; ll ans = 1; for(ll i = 0; i < n; ++i){ if(last.ff >= 0){ while(befsum+2*a[last.ff+1] <= cursum){ ++last.ff; befsum += a[last.ff]; cursum -= a[last.ff]; } } if(pre[i]-pre[last.ss] >= cursum){ befsum = cursum; cursum = pre[i]-pre[last.ss]; last.ff = last.ss; last.ss = i; ++ans; continue; } if(last.ff >= 0 && last.ss == i-1 && a[last.ff+1] >= 2*a[i] && cursum+a[i] >= befsum+a[last.ff+1]){ last.ss++; cursum += a[i]; last.ff++; cursum -= a[last.ff]; befsum += a[last.ff]; } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...