Submission #530396

#TimeUsernameProblemLanguageResultExecution timeMemory
530396jiahngCigle (COI21_cigle)C++14
48 / 100
1114 ms366244 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <ll> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MOD 1000000007 #define maxn 5001 //~ #define getchar_unlocked _getchar_nolock int N,D[maxn],ss[maxn]; inline int readInt() { int x = 0; char ch = getchar_unlocked(); while (ch < '0' || ch > '9') ch = getchar_unlocked(); while (ch >= '0' && ch <= '9'){ x = (x << 3) + (x << 1) + ch - '0'; ch = getchar_unlocked(); } return x; } vpi A[maxn]; int dp[maxn][maxn],R[maxn][maxn]; struct node{ int s,e,m,v=0, lazy=0; node *l,*r; node (int ss,int ee){ s = ss; e = ee; m = (s + e) / 2; if (s != e){ l = new node(s,m); r = new node(m+1,e); } } void prop(){ if (lazy == 0 || s == e) return; l->lazy = max(l->lazy, lazy); r->lazy = max(r->lazy, lazy); l->v = max(l->v, lazy); r->v = max(r->v, lazy); lazy = 0; } void upd(int a,int b,int c){ prop(); if (a <= s && e <= b){ v = max(v, c); lazy = max(lazy, c); }else if (a > e || s > b) return; else{ l->upd(a,b,c); r->upd(a,b,c); v = max(v, c); } } int qry(int p){ prop(); if (s == e) return v; else if (p > m) return r->qry(p); else return l->qry(p); } }*root; int32_t main() { fast; N = readInt(); FOR(i,1,N){ D[i] = readInt(); ss[i] = ss[i-1] + D[i]; } mem(R, -1); FOR(l,2,N) FOR(r,l+1,N-1) if ((ss[l-1] + ss[r]) % 2 == 0){ int ssb = (ss[l-1] + ss[r]) / 2; int b = lower_bound(ss+l,ss+r,ssb) - ss; if (ss[b] == ssb ){ //~ cout << l-1 << ' ' << b << ' ' << r << '\n'; A[b].pb(pi(l-1,r)); } } FOR(i,1,N) sort(all(A[i]), greater <pi>()); root = new node(0,N); DEC(i,N,1){ FOR(k,0,A[i].size()-1){ int newdp = dp[max(i,A[i][k].s+1)][i] + k + 1; root->upd(0, A[i][k].f - 1, newdp); } FOR(j,0,N) dp[i][j] = root->qry(j); } //~ FOR(j,0,i-1) { //~ dp[i][j] = dp[i+1][j]; //~ if (A[i][k].f > j){ // Range update max dp[i][j] from j from 0 to A[i][k].f //~ dp[i][j] = max(dp[i][j], newdp); //~ } //~ } cout << dp[1][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...