Submission #425734

#TimeUsernameProblemLanguageResultExecution timeMemory
425734egekabasBigger segments (IZhO19_segments)C++14
0 / 100
1 ms320 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]; } ll ans = 1; ll curidx = 0; ll cursum = pre[0]; for(ll i = 1; i < n; ++i){ if(pre[i]-pre[curidx] >= cursum){ while(pre[i]-pre[curidx+1] >= cursum+a[curidx+1]){ curidx++; cursum += a[curidx]; } cursum = pre[i]-pre[curidx]; curidx = i; ++ans; } } 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...