제출 #364855

#제출 시각아이디문제언어결과실행 시간메모리
364855Rainbowbunny금 캐기 (IZhO14_divide)C++17
100 / 100
44 ms6380 KiB
#include <iostream>

int n;
long long ans = 0;
long long x[100005], g[100005], d[100005];
long long suffix[100005];

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n;
	for(int i = 1; i <= n; i++)
	{
		std::cin >> x[i] >> g[i] >> d[i];
		d[i] += d[i - 1];
		g[i] += g[i - 1];
	}
	suffix[n] = d[n] - x[n];
	for(int i = n - 1; i >= 1; i--)
	{
		suffix[i] = std::max(suffix[i + 1], d[i] - x[i]);
	}
	for(int i = 1; i <= n; i++)
	{
		long long value = d[i - 1] - x[i];
		int l = 1, r = n;
		while(l < r)
		{
			int mid = (l + r + 1) >> 1;
			if(suffix[mid] >= value)
			{
				l = mid;
			}
			else
			{
				r = mid - 1;
			}
		}
		ans = std::max(ans, g[l] - g[i - 1]);
	}
	std::cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...