Submission #68591

#	Time	Username	Problem	Language	Result	Execution time	Memory
68591		cdemirer	Divide and conquer (IZhO14_divide)	C++17	100 / 100	62 ms	17796 KiB

divide

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
typedef vector<llp> vllp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define INFll 1000000000000000000ll

int N;
ll X[100000], G[100000], D[100000];
ll preG[100000], preD[100000];
ll A[100000];

int f(ll lim) {
	int l = 0, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (A[mid] <= lim) r = mid;
		else l = mid+1;
	}
	return r;
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> X[i] >> G[i] >> D[i];
	for (int i = 0; i < N; i++) preG[i] = G[i] + (i?preG[i-1]:0);
	for (int i = 0; i < N; i++) preD[i] = D[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = -X[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = min(A[i], (i?A[i-1]:INFll));
	ll ans = G[0];
	for (int i = 0; i < N; i++) {
		int l = f(preD[i]-X[i]);
		ans = max(ans, preG[i]-(l?preG[l-1]:0));
	}
	cout << ans << endl;

	return 0;
}

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