Submission #173310

#	Time	Username	Problem	Language	Result	Execution time	Memory
173310		nafis_shifat	Divide and conquer (IZhO14_divide)	C++14	17 / 100	220 ms	5112 KiB

divide

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
int main()
{
	int n;
	cin>>n;
	ll g[n+1]={};
	ll d[n+1]={};
	int x[n+1]={};
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>g[i]>>d[i];
		g[i]+=g[i-1];
		d[i]+=d[i-1];
	}

	int l=1;
	ll ans=g[1];
	for(int i=2;i<=n;i++)
	{
		if(x[i]-x[l]>d[i]-d[l-1])
		{
			while(l<i && x[i]-x[l]>d[i]-d[l-1])l++;
		}


		ans=max(ans,g[i]-g[l-1]);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52