제출 #643854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643854		ymm	금 캐기 (IZhO14_divide)	C++17	100 / 100	46 ms	14940 KiB

divide

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
struct obj { ll x, g, e, gm, em; } a[N], b[N];
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i].x >> a[i].g >> a[i].e;
	Loop (i,1,n) {
		a[i].gm = a[i-1].g;
		a[i].em = a[i-1].e;
		a[i].g += a[i].gm;
		a[i].e += a[i].em;
	}
	Loop (i,0,n) {
		a[i].e -= a[i].x;
		a[i].em -= a[i].x;
	}
	memcpy(b, a, sizeof(b));
	sort(a, a+n, [](obj &x, obj &y){return x.e < y.e;});
	sort(b, b+n, [](obj &x, obj &y){return x.em < y.em;});
	ll ans = 0;
	ll mn = 1e18;
	for (int i=0, j=0; i < n; ++i) {
		while (j < n && b[j].em <= a[i].e) {
			mn = min(mn, b[j].gm);
			++j;
		}
		ans = max(ans, a[i].g - mn);
	}
	cout << ans << '\n';
}

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