Submission #633510

#TimeUsernameProblemLanguageResultExecution timeMemory
633510uroskCigle (COI21_cigle)C++14
0 / 100
4 ms3284 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll long long #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) (ll)(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; using namespace __gnu_pbds; /* ll add(ll x,ll y){ x+=y; if(x<0){ x%=mod; x+=mod; }else{ if(x>=mod) x%=mod; } return x; } ll mul(ll a,ll b){ ll ans = (a*b)%mod; if(ans<0) ans+=mod; return ans; } */ typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rnd(ll l,ll r){ return uniform_int_distribution<ll>(l,r)(rng); } #define maxn 5005 ll n; ll a[maxn]; ll ps[maxn]; ll dpmax[maxn]; ll dp[maxn][maxn]; int main(){ daj_mi_malo_vremena cin >> n; for(ll i = 1;i<=n;i++) cin >> a[i]; for(ll l = 1;l<=n;l++){ ll j = l-1, cur = a[j]; for(ll i = 1;i<l;i++) dpmax[i] = max(dpmax[i-1],dp[i][l-1]); ll delta = 0; ll len = 0; for(ll r = l+1;r<=n;r++){ dp[l][r] = dp[l][r-1]; len+=a[r-1]; while(j>1&&cur<len)j--,cur+=a[j]; if(cur==len){ delta++; dp[l][r] = max(dp[l][r],dpmax[j-1]+delta); } } } ll ans = 0; for(ll i = 1;i<=n;i++) ans = max(ans,dp[i][n]); cout<<ans<<endl; return 0; }
#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...