Submission #371429

#TimeUsernameProblemLanguageResultExecution timeMemory
371429nicolaalexandraBigger segments (IZhO19_segments)C++14
13 / 100
1 ms384 KiB
#include <bits/stdc++.h> #define DIM 500010 #define INF 2000000000000000000LL using namespace std; int v[DIM],dp[DIM],poz[DIM]; long long sp[DIM],aint[DIM*4]; int n,i,sol; void build (int nod, int st, int dr){ aint[nod] = INF; if (st == dr) return; int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); } void update (int nod, int st, int dr, int poz, int val){ if (st == dr){ aint[nod] = val; return; } int mid = (st+dr)>>1; if (poz <= mid) update (nod<<1,st,mid,poz,val); else update ((nod<<1)|1,mid+1,dr,poz,val); aint[nod] = min (aint[nod<<1],aint[(nod<<1)|1]); } void query (int nod, int st, int dr, int val){ if (st == dr){ if (aint[nod] <= val) sol = st; return; } int mid = (st+dr)>>1; if (aint[(nod<<1)|1] <= val) query ((nod<<1)|1,mid+1,dr,val); else query ((nod<<1),st,mid,val); } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n; for (i=1;i<=n;i++){ cin>>v[i]; sp[i] = sp[i-1] + v[i]; } build (1,1,n); for (i=1;i<=n;i++){ sol = 0; query (1,1,n,sp[i]); dp[i] = dp[sol] + 1; update (1,1,n,i,2*sp[i]-sp[sol]); } cout<<dp[n]; 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...