This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long sum(int l, int r, vector<long long>& prefix){
if(l > r) return 0;
return prefix[r] - prefix[l-1];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
vector<int> a(N+1, 0);
for(int i = 1; i <= N; i++) cin >> a[i];
vector<long long> prefix(N+1, 0);
for(int i = 1; i <= N; i++) prefix[i] = prefix[i-1] + a[i];
int currAns = 0;
int ind = 0;
long long sm = 0;
for(int i = 1; i <= N; i++){
if(sum(ind + 1, i, prefix) >= sm){
long long nwSm = sum(ind + 1, i, prefix);
int lo = ind+1;
int hi = i-1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(sum(mid + 1, i, prefix) >= sm + sum(ind + 1, mid, prefix)){
nwSm = sum(mid + 1, i, prefix);
lo = mid + 1;
}else hi = mid - 1;
}
currAns++;
ind = i;
sm = nwSm;
}
}
cout << currAns << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |