Submission #1122762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122762		Tsagana	Divide and conquer (IZhO14_divide)	C++20	0 / 100	0 ms	324 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 de[100001];
int dg[100001];
int p[100001];
int g[100001];
int e[100001];

set<pair<int, int>> s;

void solve () {
	int n; cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> p[i] >> g[i] >> e[i];
		dg[i] = dg[i-1] + g[i];
		de[i] = de[i-1] + e[i];
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		s.insert({de[i-1] - p[i], -dg[i-1]});	
		pair<int, int> P = *prev(s.ub({de[i] - p[i], 1e9}));
		ans = max(ans, P.S + dg[i]);
	}
	cout << ans;
}
signed main() {IOS solve(); return 0;}

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