Submission #1006287

#TimeUsernameProblemLanguageResultExecution timeMemory
1006287andecaandeciBigger segments (IZhO19_segments)C++17
100 / 100
142 ms30336 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<ll,ll> #define REP(i,x,y) for(ll i=x;i<=y;i++) #define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #define mod 1000000000 #define pb push_back #define mk make_pair #define ll long long #define foor(x,vec) for(auto x:vec ){cout<<x<<" ";} #define fi first #define se second #define MAXN 500069 #define lld long double #define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ffl fflush(stdout) #define sst string #define pii pair<ll,ll> ll mvx[]={0,0,-1,1}; ll mvy[]={1,-1,0,0}; ll n; ll a[MAXN],b[MAXN],ps[MAXN],dp[MAXN]; ll pos[MAXN],pos2[MAXN]; vector <ll> adj[MAXN]; map<ll,ll> mp; void solve(){ cin>>n; REP(i,1,n){ cin>>a[i]; } REP(i,1,n){ ps[i]=ps[i-1]+a[i]; } dp[1]=1; REP(i,1,n){ pos[i]=max(pos[i-1],pos[i]); dp[i]=dp[pos[i]]+1; ll lb=lower_bound(ps+1,ps+n+1,ps[i]+ps[i]-ps[pos[i]])-ps; pos[lb]=i; } /* 1 1 1 2 3 0 0 0 2 4 6 8 10 18 29 ps[i]-ps[pos[i]>=ps[j]]-ps[i] ps[j]>=ps[i]*2-ps[pos[i]] ps[j]-ps[i]>=ps[i]-ps[pos[i]] ps[i]+ps[pos[i]]>=ps[j] */ cout<<dp[n]<<endl; } int main(){ ll tc; tc=1; // cin>>tc; while(tc--){ solve(); } }
#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...