Submission #1122762

#TimeUsernameProblemLanguageResultExecution timeMemory
1122762TsaganaDivide and conquer (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 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;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...