#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <string>
#include <random>
#include <chrono>
#include <memory.h>
using namespace std;
using ll = long long;
map<ll, int>idx{};
const int N = 1e5 + 3;
ll a[N];
ll st[4 * N];
void build(int l, int r, int node){
if(l == r){
st[node] = 1e18;
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2 * node + 1);
build(mid + 1, r, 2 * node + 2);
st[node] = 1e18;
}
ll query(int ql, int qr, int l, int r, int node){
if(r < ql || l > qr)
return 1e18;
if(ql <= l && r <= qr)
return st[node];
int mid = (l + r) >> 1;
return min(query(ql, qr, l, mid, 2 * node + 1), query(ql, qr, mid + 1, r, 2 * node + 2));
}
void update(int idx, int l, int r, int node){
if(idx<l||idx>r)
return;
if(l == r){
st[node] = a[idx];
return;
}
int mid = (l + r) >> 1;
update(idx, l, mid, 2 * node + 1);
update(idx, mid + 1, r, 2 * node + 2);
st[node] = min(st[2 * node + 1], st[2 * node + 2]);
}
int main()
{
//freopen("divide.in", "r", stdin);
//freopen("divide.out", "w", stdout);
int n;
cin>>n;
set<pair<ll, ll>>st;
vector<vector<ll>>arr;
vector<ll> sorted;
ll pref = 0;
for(int i = 0; i < n; i++){
ll x,g,d;
cin>>x>>g>>d;
arr.push_back({x, g, d});
sorted.push_back(x - pref);
pref += d;
}
sort(sorted.begin(), sorted.end());
for(int i = 0; i < n; i++){
idx[sorted[i]] = i;
}
build(0, n - 1, 0);
fill(a, a + N, 1e18);
ll gold = 0, energy = 0, ans = 0;
for(int i = 0; i < n; i++){
ll x = arr[i][0], g = arr[i][1], d = arr[i][2];
int ref = idx[x - energy];
a[ref] = min(a[ref], gold);
update(ref, 0, n - 1, 0);
gold += g, energy += d;
ans = max(ans, gold - query(ref, n - 1, 0, n - 1, 0));
}
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
