Submission #474854

#TimeUsernameProblemLanguageResultExecution timeMemory
474854ismoilov금 캐기 (IZhO14_divide)C++14
100 / 100
50 ms7884 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...