제출 #216998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216998		lukameladze	Bigger segments (IZhO19_segments)	C++14	13 / 100	6 ms	384 KiB

segments

# include <bits/stdc++.h>
using namespace std;
long long n,a[500005],sum[500005],le,ri,mid,ans;
pair <long long , long long> dp[500005];
int main()
{
     cin>>n;
     for (int i=1; i<=n; i++)
     {
          cin>>a[i];
          sum[i]=sum[i-1]+a[i];
     }
     for (int i=1; i<=n; i++)
     {
     	le=0;
     	ri=i-1;
     	ans=0;
     	while (le<=ri)
     	{
     		mid=(le+ri)/2;
     		if (sum[i]-sum[mid]>=dp[mid].second)
			{
			 	ans=mid;
			 	le=mid+1;
			}
			else ri=mid-1;	
		}
		for (int j=ans; j>=0; j--)
		{
			if (dp[i].first<=dp[j].first && sum[i]-sum[j]>=dp[j].second)
			{
				dp[i].first=dp[j].first+1;
				dp[i].second=sum[i]-sum[j];
				//break;
			}
		}
     }
     cout<<dp[n].first<<endl;
}

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