Submission #39079

#	Time	Username	Problem	Language	Result	Execution time	Memory
39079		mrtsima22	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1000 ms	6080 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define lo long
lo d[100003],j[100003];
lo g[100003],ans,h[100003];
lo x[100003],n;
int main(){std::ios::sync_with_stdio(false);
//	ifstream cin("devide.in");
//	ofstream cout("devide.out");
cin>>n;
for(lo i=0;i<n;i++)
{
	cin>>x[i]>>g[i]>>d[i];
	j[i]=j[i-1]+d[i];
//	cout<<j[i]<<" ";
	h[i]=h[i-1]+g[i];
//	cout<<h[i]<<endl;
}
for(lo i=0;i<n;i++)
{
	for(lo q=i;q<n;q++)
	{
//		cout<<j[q]<<" "<<j[i]<<" "<<x[q]<<" "<<x[i]<<" +++++"<<endl;
		if(j[q]-j[i-1]>=x[q]-x[i])
		{
			ans=max(ans,h[q]-h[i-1]);
		}
	}
}
cout<<ans<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/

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