Submission #1122763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122763		Tsagana	Divide and conquer (IZhO14_divide)	C++20	100 / 100	58 ms	10568 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;
	int mn = INT_MAX;
	for (int i = 1; i <= n; i++) {
		if (de[i-1] - p[i] < mn) {
			mn = de[i-1] - p[i];
			s.insert({mn, -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: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52