제출 #170954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170954		Lightning	금 캐기 (IZhO14_divide)	C++14	100 / 100	96 ms	9976 KiB

divide

#pragma GCC optimize ("O3")
#pragma GCC target ("avx,avx2")

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<" "
#define shown(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
#define int ll

const int szT = (1 << 17) - 1;
const int INF = 1e9;

struct rudina {
	int x, g, e;
} a[szT];

int t[szT * 4];
int add[szT * 4];

void push(int v, int tl, int tr) {
	if(add[v]) {
		t[v] += add[v];
		if(tl < tr) {
			add[v * 2] += add[v];
			add[v * 2 + 1] += add[v];
		}
		add[v] = 0ll;
	}
}

void upd(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		add[v] += x;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, x);
	upd(v * 2 + 1, tm + 1, tr, l, r, x);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int tl, int tr) {
	push(v, tl, tr);
	if(tl == tr) {	
		//show(tl);
		return tl;
	}
	int tm = (tl + tr) / 2;
	if(t[v * 2] + add[v * 2] >= 0ll) return get(v * 2, tl, tm);
	else return get(v * 2 + 1, tm + 1, tr);
}

/*int get2(int v, int tl, int tr) {
	push(v, tl, tr);
	if(tl == tr) {	
		//show(tl);
		return tl;
	}
	int tm = (tl + tr) / 2;
	if(t[v * 2] + add[v * 2] >= 0ll) return get2(v * 2, tl, tm);
	else return get2(v * 2 + 1, tm + 1, tr);
}*/

int n, ans, pref[szT];

main () {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].g >> a[i].e;
		pref[i] = pref[i - 1] + a[i].g;
	}	
	int lastx = 0;
	for(int r = 1; r <= n; ++r) {
		upd(1, 1, n, 1, r, a[r].e);
		if(1 < r) upd(1, 1, n, 1, r - 1, -(a[r].x - lastx));
		int l = get(1, 1, n);			
		//show(l); show(r); show(pref[r] - pref[l - 1]), shown(get2(1, 1, n));
		ans = max(ans, pref[r] - pref[l - 1]); 
		lastx = a[r].x;
	}
	cout << ans;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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