Submission #364855

#	Time	Username	Problem	Language	Result	Execution time	Memory
364855		Rainbowbunny	Divide and conquer (IZhO14_divide)	C++17	100 / 100	44 ms	6380 KiB

divide

#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;
}

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