Submission #526255

#	Time	Username	Problem	Language	Result	Execution time	Memory
526255		maks007	Divide and conquer (IZhO14_divide)	C++14	100 / 100	120 ms	7496 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)(1e18)
vector <int> t;
int k = 1;

void update(const int val, const int pos, int vl = 0, int vr = k - 1, int v = 0) {
	if(vl == vr) {
		t[v] = val;
		return;
	}
	int vm = (vl + vr) >> 1;
	if(pos <= vm) update(val, pos, vl, vm, 2*v+1);
	else update(val, pos, vm+1, vr, 2*v+2);
	t[v] = min(t[2*v+1], t[2*v+2]);
}

int get(int x, int vl = 0, int vr = k - 1, int v = 0) {
	if(vl == vr) return vl;
	else {
		int vm = (vl+vr) >> 1;
		if(x >= t[2*v+1]) {
			return get(x, vl, vm, 2*v+1);
		}else return get(x, vm+1, vr, 2*v+2);
	}
}

int32_t main(void) {
	int n;
	cin >> n;
	while(k < n) k <<= 1;
	t.resize(2*k-1, inf);
	vector <int> energy(n), gold(n), a(n);
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
		int ener, gol;
		cin >> gol >> ener;
		update((i-1<0?0:energy[i-1]) - a[i], i);
		if(i == 0) energy[i] = ener;
		else energy[i] = energy[i - 1] + ener;
		if(i == 0) gold[i] = gol;
		else gold[i] = gold[i - 1] + gol;
	}
	int mx = 0;
	for(int i = 0; i < n; i ++) {
		int ss = get(energy[i] - a[i]);
		mx = max(mx, gold[i] - (ss-1<0?0:gold[ss-1]));
	}
	cout << mx;
	return false;
}

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