Submission #1122740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122740		Tsagana	Divide and conquer (IZhO14_divide)	C++20	0 / 100	1 ms	328 KiB

divide

#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--) if (l[i].S < l[i+1].S) 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--) if (r[i].S < r[i+1].S) r[i] = r[i+1];

	// for (auto i: l) cout << "l: " << i.F << ' ' << i.S << '\n';
	// for (auto i: r) cout << "r: " << i.F << ' ' << i.S << '\n';

	L = l.size()-1, R = 0;
	while (L && R < r.size()) {
		while (L && l[L].S + r[R].S < d) L--;
		if (L) ans = max(ans, r[R].F + l[L].F);
		// cout << d << ' ' << l[L].S + r[R].S << ' ' << r[R].F + l[L].F << '\n';
		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;}

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