Submission #1040405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040405		vjudge1	Divide and conquer (IZhO14_divide)	C++14	100 / 100	67 ms	10348 KiB

divide

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	long long a[n+2],b[n+1],c[n+1],d[n+1],f[n+1],g[n+1];
	int h[n+1];
	for(int i=0;i<n;i++)
	{
	    cin >> a[i+1] >> b[i+1] >> c[i+1];
	}
	a[n+1]=a[n];a[0]=0;b[0]=0;c[0]=a[1]-a[0];d[0]=c[0];g[0]=0;f[0]=0;
	for(int i=1;i<=n;i++)
	{
	    g[i]=g[i-1]+b[i];
	    d[i]=c[i]+d[i-1];
	    f[i]=d[i]-a[i+1];
	}
	vector<pair<long long,int> > v;
	for(int i=0;i<=n;i++)
	{
	    v.push_back({f[i],i});
	}
	sort(v.begin(),v.end());/*
	for(int i=0;i<=n;i++)
	{
	    cout << v[i].first << ' ' << v[i].second << '\n';
	}
	cout << endl;
	/**/
	long long res=0;
	h[0]=v[0].second;
	for(int i=1;i<=n;i++) h[i]=min(h[i-1],v[i].second);
	for(int i=0;i<=n;i++)
	{
	    long long x=v[i].first+a[v[i].second+1]-a[v[i].second];
	    //cout << x << ' ' ;
	    int l=0,r=i-1,ans=1000000000;
	    while(l<=r)
	    {
	        int g=(l+r)/2;
	        if(v[g].first<=x)
	        {
	            ans=min(ans,h[g]);
	            l=g+1;
	        }
	        else r=g-1;
	    }
	    l=i+1;r=n;
	    while(l<=r)
	    {
	        int g=(l+r)/2;
	        if(v[g].first<=x)
	        {
	            ans=min(ans,h[g]);
	            l=g+1;
	        }
	        else r=g-1;
	    }
	    //cout << ans << '\n';
	    if(ans>n||ans>v[i].second)
	    {
	        continue;
	    }
	    res=max(res,g[v[i].second]-g[ans]);
	}
	cout << res;
	return 0;
}

/*

2
0 4 1
3 5 1

2
1 4 2
3 5 0

*/

Compilation message (stderr)

divide.cpp:32:2: warning: "/*" within comment [-Wcomment]
   32 |  /**/
      |

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