#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100000 + 7;
typedef long long ll;
const ll infll = 1e15;
int x[maxn];
int g[maxn];
int d[maxn];
ll pr_d[maxn];
ll pr_g[maxn];
struct Node {
ll l, r;
ll val;
Node* left;
Node* right;
Node(ll val_, ll l_, ll r_) {
val = val_;
l = l_;
r = r_;
left = nullptr;
right = nullptr;
}
};
void pull(Node* root) {
if (root->left != nullptr) {
root->val = min(root->val, root->left->val);
}
if (root->right != nullptr) {
root->val = min(root->val, root->right->val);
}
}
void add(Node* root, ll val, ll ind) {
if (root->l == ind && root->r == ind + 1) {
root->val = min(val,root->val);
return;
}
ll m = (root->l + root->r) / 2;
if (ind < m) {
if (root->left == nullptr) {
root->left = new Node(val, root->l, m);
}
add(root->left, val, ind);
}
else {
if (root->right == nullptr) {
root->right = new Node(val, m, root->r);
}
add(root->right, val, ind);
}
pull(root);
}
ll get(Node* root, ll l, ll r) {
if (root->l >= r || root->r <= l) {
return infll;
}
if (root->l >= l && root->r <= r) {
return root->val;
}
ll ans = infll;
if (root->left != nullptr) {
ans = min(ans, get(root->left, l, r));
}
if (root->right == nullptr) {
ans = min(ans, get(root->right, l, r));
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> g[i] >> d[i];
}
vector<pair<ll, ll>> q;
for (int i = 0; i < n; i++) {
pr_d[i] = (i>0?pr_d[i-1]:0) + d[i];
pr_g[i] = (i > 0 ? pr_g[i - 1] : 0) + g[i];
}
Node* root = new Node(infll, -infll, infll);
ll gold = 0;
for (int i = 0; i < n; i++) {
ll val = (i > 0 ? pr_g[i - 1] : 0);
ll ind = (i > 0 ? pr_d[i - 1] : 0) - x[i];
q.emplace_back(((i>0?pr_d[i - 1]:0) - x[i]),(i>0?pr_g[i-1]:0));
add(root, val, ind);
ll cur = pr_d[i] - x[i];
/*for (auto t : q) {
if (cur >= t.first) {
gold = max(gold, pr_g[i] - t.second);
}
}*/
gold = max(gold, pr_g[i] - get(root, -infll, cur+1));
}
cout << gold;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
