Submission #213170

#	Time	Username	Problem	Language	Result	Execution time	Memory
213170		islingr	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1089 ms	5624 KiB

divide

#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);
	rep(i, 0, n) {
		cin >> x[i] >> g[i + 1] >> e[i + 1];
		g[i + 1] += g[i];
		e[i + 1] += e[i];
	}

	ll ans = 0;
	rep(i, 0, n) {
		int j = 0;
		for (; j < i; ++j)
			if (x[i] - x[j] <= e[i + 1] - e[j])
				break;
		ckmax(ans, g[i + 1] - g[j]);
	}
	cout << ans;
}

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