Submission #777011

#	Time	Username	Problem	Language	Result	Execution time	Memory
777011		khoquennguoiminhthuong	Bigger segments (IZhO19_segments)	C++14	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];
void upd(int id,long long val)
{
while(id>0)
{
tree[id]=min(tree[id],val);id-=(id&(-id));
}
}
int pre[500005];
int getmin(int id)
{
long long minn=1e18;
while(id<=n+1)
{
minn=min(minn,tree[id]);
id+=(id&(-id));
}
return minn;
}
int ans=0;
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];}
dp[0]=0;
dp[1]=a[1];
int dd=0;
for(int i=1;i<=n+1;i++)tree[i]=2e9;
upd(1,0);
upd(2,2*a[1]);
for(int i=2;i<=n;i++)
{
while(dd<i-1&&tong[i]>=getmin(dd+2))dd++;
dp[i]=tong[i]-tong[dd];
pre[i]=dd;
upd(i+1,dp[i]+tong[i]);
}
int v=n;
while(v>0)
{
v=pre[v];
ans++;
}
cout<<ans;
    return 0;
}

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