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 int inf = 5009;
int n,a[inf],dp[inf][inf],mx[inf],ans;
vector<pair<int,int> > v[inf];
int get(vector<pair<int,int> > &cur,int ub){
// int ret = 0;
// for(auto o:cur)
// if(o.first <= ub)
// ret = max(ret,o.second);
// return ret;
int idx = lower_bound(cur.begin(),cur.end(),make_pair(ub+1,-1))-cur.begin();
if(idx-1 >=0 && cur[idx-1].first <= ub)
return cur[idx-1].second;
return 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<n;i++){
int l = i,sum1 = a[l],sum2 = 0,cur = 0;
for(int r = i+1;r<n;r++){
sum2 += a[r];
while(l>1 && sum1 + a[l-1] <= sum2)
sum1 += a[l-1],l--;
if(sum1 == sum2)cur++;
dp[i][r+1] = dp[i][r];
int mx = 0;
if(l != 1)
mx = get(v[i],l-2),dp[i][r+1] = max(dp[i][r+1],mx + cur);
pair<int,int> tmp = (v[r+1].empty()?make_pair(0,0):v[r+1].back());
tmp.first = i,tmp.second = max(tmp.second,dp[i][r+1]);
v[r+1].push_back(tmp);
ans = max(ans,dp[i][r+1]);
}
}
cout<<ans<<endl;
}
# | 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... |