Submission #1122736

#TimeUsernameProblemLanguageResultExecution timeMemory
1122736Tsagana금 캐기 (IZhO14_divide)C++20
0 / 100
0 ms324 KiB
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int G[100001];
int E[100001];
int A[100001];
int n;

int calc(int L, int R) {
	int ans = 0;
	vector<pair<int, int>> l, r;

	int M = (L + R) / 2;
	int d = A[M+1] - A[M];
	
	int e = 0, g = 0;
	for (int i = M; i >= L; i--) {
		e += E[i]; g += G[i];
		l.pb({g, e - (A[M] - A[i])});
	}
	for (int i = l.size()-2; i >= 0; i--) l[i] = max(l[i], l[i+1]);

	e = 0; g = 0;
	for (int i = M + 1; i <= R; i++) {
		e += E[i]; g += G[i];
		r.pb({g, e - (A[i] - A[M + 1])});
	}
	for (int i = r.size()-2; i >= 0; i--) r[i] = max(r[i], r[i+1]);

	L = l.size()-1, R = 0;
	while (L && R < r.size()) {
		while (L && l[L].S + r[R].S - d < 0) L--;
		if (L) ans = max(ans, r[R].F + l[L].F);
		R++;
	}
	return ans;
}

int find(int L, int R) {
	if (L == R) return G[L];
	int M = (L + R) / 2;
	int LA = find(L, M);
	int RA = find(M + 1, R);
	int MA = calc(L, R);
	return max({LA, MA, RA});
}

void solve () {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i] >> G[i] >> E[i];
	}
	// cout << calc(0, n - 1) << endl;
	cout << find(0, n-1) << endl;
}
signed main() {IOS solve(); return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...