Submission #777028

#	Time	Username	Problem	Language	Result	Execution time	Memory
777028		khoquennguoiminhthuong	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	340 KiB

segments

#include <bits/stdc++.h>

using namespace std;
int a[500005];
int n;
long long tong[500005];
long long dp[500005];
long long tree[500005];
long long f[500005];
void upd(int id,long long val)
{
while(id>0)
{
tree[id]=min(tree[id],val);id-=(id&(-id));
}
}
int getmin(int id)
{
long long minn=1e18;
while(id<=n+1)
{
minn=min(minn,tree[id]);
id+=(id&(-id));
}
return minn;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];tong[i]=tong[i-1]+a[i];}
int dd=0;
for(int i=1;i<=n+1;i++)tree[i]=1e18;
dp[0]=0;
dp[1]=1;
upd(1,0);
upd(2,1LL*2*a[1]);
for(int i=2;i<=n;i++)
{
while(dd<i-1&&tong[i]>=getmin(dd+2)){dd++;}
long long v=tong[i]-tong[dd];
dp[i]=dp[dd]+1;
upd(i+1,v+tong[i]);
}
cout<<dp[n];
    return 0;
}
/*
tong[i]-tong[j-1]>=dp[j-1];
tong[i]>=dp[j-1]+tong[j-1];
*/

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27