Submission #91000

#	Time	Username	Problem	Language	Result	Execution time	Memory
91000		Nodir_Bobiev	Divide and conquer (IZhO14_divide)	C++14	100 / 100	40 ms	8808 KiB

divide

# include <bits/stdc++.h>

# define ll long long
# define fi first
# define se second

using namespace std;

const ll  INF = 8e18 + 10;
const ll  MOD = 1e9 + 7;
const int N = 1e5 + 10;
const int Z = 5e4 + 10;

ll n;
ll x[N], g[N], e[N], pf[N], ans;

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> x[i] >> g[i] >> e[i];
		g[i] += g[i - 1];
		e[i] += e[i - 1];
		pf[i] = min(pf[i - 1], e[i - 1] - x[i]);
		//cout << pf[i] << ' ';
	}
	
	for (int i = 1; i <= n; i++){
		int l = 1, m, r = i;
		ans = max(ans, g[i] - g[i - 1]);
		
		while(r >= l){
			m = (l + r) >> 1;
			
			if(pf[m] <= e[i] - x[i]){
				ans = max(ans, g[i] - g[m - 1]);
				r = m - 1;
			}
			else 
				l = m + 1;
		}
	}
	cout << ans;
}


int main()
{
	int TE = 1;
	ios_base::sync_with_stdio(false);
	//freopen("sort.in", "r", stdin);
	//freopen("sort.out", "w", stdout);
	//cin >> TE;
	
	while(TE --)
		solve();
	
	return 0;
}

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