Submission #419307

#TimeUsernameProblemLanguageResultExecution timeMemory
419307Runtime_error_Cigle (COI21_cigle)C++14
100 / 100
868 ms197176 KiB
#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 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...