Submission #213172

#TimeUsernameProblemLanguageResultExecution timeMemory
213172islingrDivide and conquer (IZhO14_divide)C++14
48 / 100
1099 ms6392 KiB
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define ff first
#define ss second

using ll = int64_t;

template<class T> bool ckmin(T &a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T& b) { return a < b ? a = b, 1 : 0; }

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	vector<ll> x(n), g(n + 1), e(n + 1), diff(n);
	rep(i, 0, n) {
		cin >> x[i] >> g[i + 1] >> e[i + 1];
		g[i + 1] += g[i];
		e[i + 1] += e[i];
		diff[i] = x[i] - e[i];
	}

	ll ans = 0;
	rep(i, 0, n) {
		int j = 0;
		for (; j < i; ++j)
			if (x[i] - e[i + 1] <= diff[j])
				break;
		ckmax(ans, g[i + 1] - g[j]);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...