oj.uz

답안 #216997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216997 2020-03-28T16:47:28 Z lukameladze Bigger segments (IZhO19_segments) C++14
0 / 100
 4 ms 384 KB 
# 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+10; 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
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -