Submission #42486

#	Time	Username	Problem	Language	Result	Execution time	Memory
42486		MatheusLealV	Divide and conquer (IZhO14_divide)	C++14	100 / 100	44 ms	9160 KiB

divide

#include <bits/stdc++.h>
#define inf 2000000000000000000LL
#define N 200050
#define f first
using namespace std;
typedef long long ll;
 
ll cnt = 2;
 
ll n, sum[N], g[N], x[N], E[N], dp[N], ans, pref[N];
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n;
 
	for(int i = 1; i <= n; i++)
	{
		cin>>x[i]>>g[i]>>E[i];
 
		sum[i] = E[i] + sum[i - 1];
 
		g[i] += g[i - 1];
	}

	pref[0] = inf;
  
	for(int i = 1; i <= n; ++i) pref[i] = min(pref[i - 1], sum[i - 1] - x[i]);

	for(int i = 1; i <= n; i++)
	{
		int ini = 1, fim = i, mid, best = i;

		while(fim >= ini)
		{
			mid = (ini + fim)/2;

			if(pref[mid] <= sum[i] - x[i]) best = mid, fim = mid - 1;

			else ini = mid + 1;
		}

		ans = max(ans, g[i] - g[best - 1]);
	}
 
	cout<<ans<<"\n";
}

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