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;
const long long int N=1e9+7;
int main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios::sync_with_stdio(0); cin.tie(nullptr);
int n;
cin>>n;
vector<int>a(n),prf(n+1);
for(int i=0;i<n;i++)
{
cin>>a[i];
prf[i+1]=a[i]+(i>1 ? prf[i]:0);
}
vector<pair<int,int>>dp(n+1,{-1e9,0});
dp[0]={0,0};
for(int i=0;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
int vl=prf[j];
if(dp[i].second+prf[i]<=vl)
dp[j]={dp[i].first+1,vl};
}
}
cout<<dp[n].first<<endl;
return 0;
}
/*
0 0
0 0
0 0
0 0
*/
# | 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... |