#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
const int MAXN = 1e5+5;
#define INF 100000000
int main() {
int n;
cin >> n;
vector<ll> dp(MAXN), energy(MAXN), gold(MAXN), pos(MAXN);
dp[0] = 0;
gold[0] = 0;
energy[0] = 0;
pos[0] = 0;
multiset<ll> 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;
ll 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] });
ll 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
