Submission #68591

#TimeUsernameProblemLanguageResultExecution timeMemory
68591cdemirerDivide and conquer (IZhO14_divide)C++17
100 / 100
62 ms17796 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
typedef vector<llp> vllp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define INFll 1000000000000000000ll

int N;
ll X[100000], G[100000], D[100000];
ll preG[100000], preD[100000];
ll A[100000];

int f(ll lim) {
	int l = 0, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (A[mid] <= lim) r = mid;
		else l = mid+1;
	}
	return r;
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> X[i] >> G[i] >> D[i];
	for (int i = 0; i < N; i++) preG[i] = G[i] + (i?preG[i-1]:0);
	for (int i = 0; i < N; i++) preD[i] = D[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = -X[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = min(A[i], (i?A[i-1]:INFll));
	ll ans = G[0];
	for (int i = 0; i < N; i++) {
		int l = f(preD[i]-X[i]);
		ans = max(ans, preG[i]-(l?preG[l-1]:0));
	}
	cout << ans << endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...