제출 #1002887

#제출 시각아이디문제언어결과실행 시간메모리
1002887LalicCigle (COI21_cigle)C++17
48 / 100
1050 ms394276 KiB
#include <bits/stdc++.h> #pragma GCC optimize "O3" using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define mp make_pair #define int long long typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<double> cd; const int MAXN = 5e3+10; const int MOD = 1e9+7; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; const double PI = acos(-1); int tree[MAXN][4*MAXN], lazy[MAXN][4*MAXN]; void lazyP(int id, int node, int l, int r){ if(!lazy[id][node]) return; tree[id][node]+=lazy[id][node]; if(l!=r){ lazy[id][node*2]+=lazy[id][node]; lazy[id][node*2+1]+=lazy[id][node]; } lazy[id][node]=0; } void upd(int id, int node, int l, int r, int p, int q, int val){ lazyP(id, node, l, r); if(r<p || l>q) return; if(l>=p && r<=q){ lazy[id][node]+=val; lazyP(id, node, l, r); return; } int mid=(l+r)>>1; upd(id, node*2, l, mid, p, q, val); upd(id, node*2+1, mid+1, r, p, q, val); tree[id][node]=max(tree[id][node*2], tree[id][node*2+1]); } int query(int id, int node, int l, int r, int p, int q){ lazyP(id, node, l, r); if(r<p || l>q) return 0; if(l>=p && r<=q) return tree[id][node]; int mid=(l+r)>>1; return max(query(id, node*2, l, mid, p, q), query(id, node*2+1, mid+1, r, p, q)); } void solve(){ int n; cin >> n; vector<int> arr(n+1); for(int i=1;i<=n;i++) cin >> arr[i]; for(int i=3;i<=n;i++){ int sum=arr[i], c2=i-2, tot=arr[i-1]; for(int c1=i-1;c1>=0;c1--){ upd(i, 1, 0, n, c1, c1, query(c1, 1, 0, n, 0, n)); while(c2>0 && tot<sum){ tot+=arr[c2]; c2--; } if(tot==sum && c2>0) upd(c1, 1, 0, n, 0, c2-1, 1); sum+=arr[c1]; tot-=arr[c1]; } } cout << query(n, 1, 0, n, 0, n) << "\n"; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int tt=1; //~ cin >> tt; while(tt--) solve(); 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...