제출 #167786

#제출 시각아이디문제언어결과실행 시간메모리
167786Gurban금 캐기 (IZhO14_divide)C++11
0 / 100
303 ms14328 KiB
#include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2

using namespace std;

int n,pos;
ll T[4 * N][5],x,g,e,go[N],mx;

void upd(int val,int a,int b,int l,int r,int nd){
	T[nd][0] += T[nd / 2][1];
	T[nd][1] += T[nd / 2][1];
	if(l >= a and r <= b){
		T[nd][0] += val;
		T[nd][1] += val;
		return;
	}
	if(l > b or r < a)
		return;
	upd(val,a,b,l,mid(l,r),nd * 2);
	upd(val,a,b,mid(l,r) + 1,r,nd * 2 + 1);
	T[nd][1] = 0;
	T[nd][0] = max(T[nd * 2][0],T[nd * 2 + 1][0]);
}
int tap(int x,int l,int r,int nd){
	if(l == r)
		return l;
	T[nd * 2][0] += T[nd][1];
	T[nd * 2][1] += T[nd][1];
	T[nd * 2 + 1][0] += T[nd][1];
	T[nd * 2 + 1][1] += T[nd][1];
	T[nd][1] = 0;
	if(T[nd * 2][0] >= x)
		return tap(x,l,mid(l,r),nd * 2);
	return tap(x,mid(l,r) + 1,r,nd * 2 + 1);
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> x >> g >> e;
		go[i] = go[i - 1] + g;
		upd(e,1,i - 1,1,n,1);
		pos = tap(x,1,n,1);
		upd(x+e,i,i,1,n,1);
		mx = max(go[i] - go[pos - 1],mx);
	}	
	cout << mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...