제출 #308166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
308166		shrek12357	금 캐기 (IZhO14_divide)	C++14	0 / 100	2 ms	1920 KiB

divide

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
#define ll long long

vector<ll> nums;
const int MAXN = 1e5+5;
#define INF 10000000000

int main() {
	int n;
	cin >> n;
	vector<int> dp(MAXN), energy(MAXN), gold(MAXN), pos(MAXN);
	dp[0] = 0;
	gold[0] = 0;
	energy[0] = 0;
	pos[0] = 0;
	multiset<int> nums;
	for (int i = 0; i < n; i++) {
		int x, g, e;
		cin >> x >> g >> e;
		gold[i + 1] = gold[i] + g;
		energy[i + 1] = e;
		pos[i + 1] = x;
		if (i == 0) {
			dp[i + 1] = e;
		}
		else {
			dp[i + 1] = dp[i] + e - pos[i + 1] + pos[i];
		}
		nums.insert(dp[i + 1] * -1);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;

	int best = 0;

	for (int i = 1; i <= n; i++) {
		if (i == n) {
			best = max(best, gold[i] - gold[i - 1]);
			continue;
		}
		nums.erase(nums.find(-1 * dp[i]));
		pq.push({ energy[i] - dp[i], gold[i - 1] });
		int mxVal = *nums.begin() * -1;
		while (pq.size() > 0 && pq.top().first > mxVal) {
			best = max(gold[i] - pq.top().second, best);
			pq.pop();
		}
	}

	cout << best << endl;
}

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