제출 #1122621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122621		Tsagana	금 캐기 (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, ans = 0;

void calc(int L, int R) {
	vector<pair<int, int>> l, r;
	l.clear();
	r.clear();

	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];


	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++;
	}
}

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

void solve () {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i] >> G[i] >> E[i];
	}
	
	find(0, n-1);
	cout << ans;
}
signed main() {IOS solve(); return 0;}

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