Submission #474854

#	Time	Username	Problem	Language	Result	Execution time	Memory
474854		ismoilov	Divide and conquer (IZhO14_divide)	C++14	100 / 100	50 ms	7884 KiB

divide

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int maxx = 1e5+5;

ll x[maxx], g[maxx], d[maxx], pr[maxx], prr[maxx], mn[maxx];

void S()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> x[i] >> g[i] >> d[i];
		pr[i] = pr[i-1] + g[i];
		prr[i] = prr[i-1] + d[i];
		mn[i] = min(mn[i-1], prr[i-1] - x[i]);
	}
	ll mx = 0;
	for(int i = 0; i < n; i ++){
		int l = 0, r = i, ans = i;
		while(l <= r){
			int m = (l+r) / 2;
			if(mn[m] <= prr[i] - x[i])
				r = m-1, ans = m;
			else
				l = m+1;
		}
		mx = max(mx, pr[i] - pr[ans - 1]);
	}
	cout << mx;
}

int main()
{
	IOS;
	/*int t;
	cin >> t;
	while(t --)*/
		S();
}

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