Submission #1166917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166917		Muaath_5	Divide and conquer (IZhO14_divide)	C++20	100 / 100	28 ms	6844 KiB

divide

// Problem: I - Знате
// Contest: Virtual Judge - 2024-03-11
// URL: https://vjudge.net/contest/700556#problem/I
// 
// By Muaath Alqarni
// Blog: https://muaath.dev/blog

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
using namespace std;

const int N = 2e5+1;
const ll INF = 1e18;

int n;
array<ll, 3> a[N];

ll pref[N], prefg[N];

ll prefmn[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; cin >> a[i][0] >> a[i][1] >> a[i][2], i++);
	sort(a+1, a+n+1);
	a[0][0] = a[1][0];
	a[n+1][0] = a[n][0];
	vector<pii> v;
	v.push_back({0, 0});
	for (int i = 1; i <= n; i++) {
		pref[i] = pref[i-1] - (a[i][0] - a[i-1][0]) + a[i][2];
		prefg[i] = prefg[i-1] + a[i][1];
		v.push_back({pref[i] - (a[i+1][0] - a[i][0]), prefg[i]});
	}
	sort(v.begin(), v.end());
	for (int i = 0; i <= n; i++) {
		prefmn[i] = min(i ? prefmn[i-1] : INF, v[i].second);
	}
	ll sol = 0;
	for (int r = 1; r <= n; r++) {
		int idx = upper_bound(v.begin(), v.end(), pii{pref[r], INF})-v.begin()-1;
		ll ans = prefg[r] - prefmn[idx];
		sol = max(sol, ans);
	}
	cout << sol;
}

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