제출 #42486

#제출 시각아이디문제언어결과실행 시간메모리
42486MatheusLealV금 캐기 (IZhO14_divide)C++14
100 / 100
44 ms9160 KiB
#include <bits/stdc++.h>
#define inf 2000000000000000000LL
#define N 200050
#define f first
using namespace std;
typedef long long ll;
 
ll cnt = 2;
 
ll n, sum[N], g[N], x[N], E[N], dp[N], ans, pref[N];
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n;
 
	for(int i = 1; i <= n; i++)
	{
		cin>>x[i]>>g[i]>>E[i];
 
		sum[i] = E[i] + sum[i - 1];
 
		g[i] += g[i - 1];
	}

	pref[0] = inf;
  
	for(int i = 1; i <= n; ++i) pref[i] = min(pref[i - 1], sum[i - 1] - x[i]);

	for(int i = 1; i <= n; i++)
	{
		int ini = 1, fim = i, mid, best = i;

		while(fim >= ini)
		{
			mid = (ini + fim)/2;

			if(pref[mid] <= sum[i] - x[i]) best = mid, fim = mid - 1;

			else ini = mid + 1;
		}

		ans = max(ans, g[i] - g[best - 1]);
	}
 
	cout<<ans<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...