#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>
struct Point {
int32_t x;
int32_t gold, energy;
};
struct Node {
Node* left = nullptr, *right = nullptr;
int32_t priority;
int64_t key;
int32_t value;
int32_t min_value;
Node(int64_t key_, int32_t value_) {
key = key_;
value = value_;
min_value = value;
}
};
void recalc(Node* node) {
node->min_value = node->value;
if(node->left != nullptr)
node->min_value = std::min(node->min_value, node->left->min_value);
if(node->right != nullptr)
node->min_value = std::min(node->min_value, node->right->min_value);
}
std::pair<Node*, Node*> split(Node* node, int64_t x) {
if(node == nullptr)
return {nullptr, nullptr};
if(node->key < x) {
std::pair<Node*, Node*> res = split(node->right, x);
node->right = res.first;
recalc(node);
return {node, res.second};
} else {
std::pair<Node*, Node*> res = split(node->left, x);
node->left = res.second;
recalc(node);
return {res.first, node};
}
}
Node* merge(Node* node1, Node* node2) {
if(node1 == nullptr)
return node2;
if(node2 == nullptr)
return node1;
if(node1->priority < node2->priority) {
node1->right = merge(node1->right, node2);
recalc(node1);
return node1;
} else {
node2->left = merge(node1, node2->left);
recalc(node2);
return node2;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int32_t n;
std::cin >> n;
Point* points = new Point[n];
for(int32_t i = 0; i < n; i++)
std::cin >> points[i].x >> points[i].gold >> points[i].energy;
int64_t* pref_sum = new int64_t[n + 1];
pref_sum[0] = 0;
for(int32_t i = 1; i <= n; i++)
pref_sum[i] = pref_sum[i - 1] + points[i - 1].energy;
int64_t* gold_pref_sum = new int64_t[n + 1];
gold_pref_sum[0] = 0;
for(int32_t i = 1; i <= n; i++)
gold_pref_sum[i] = gold_pref_sum[i - 1] + points[i - 1].gold;
int64_t ans = 0;
Node* root = nullptr;
for(int32_t i = 0; i < n; i++) {
std::pair<Node*, Node*> parts = split(root, points[i].x - pref_sum[i]);
root = merge(merge(parts.first, new Node(points[i].x - pref_sum[i], i)), parts.second);
int64_t val = points[i].x - pref_sum[i + 1];
parts = split(root, val);
ans = std::max(ans, gold_pref_sum[i + 1] - gold_pref_sum[parts.second->min_value]);
root = merge(parts.first, parts.second);
}
std::cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
12 ms |
416 KB |
Output is correct |
19 |
Correct |
10 ms |
332 KB |
Output is correct |
20 |
Correct |
8 ms |
416 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
12 ms |
416 KB |
Output is correct |
19 |
Correct |
10 ms |
332 KB |
Output is correct |
20 |
Correct |
8 ms |
416 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
588 KB |
Output is correct |
25 |
Correct |
200 ms |
820 KB |
Output is correct |
26 |
Correct |
808 ms |
1412 KB |
Output is correct |
27 |
Correct |
819 ms |
1320 KB |
Output is correct |
28 |
Execution timed out |
1077 ms |
2440 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |