#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 100005, LEAF = 1<<17;
int N, X[N_], G[N_], D[N_];
ll SG[N_], SD[N_];
ll res;
int O[N_], W[N_];
ll V[N_];
bool cmpO(const int &a, const int &b) { return V[a] < V[b]; }
ll Tree[N_+LEAF];
void update (int x, ll v) {
Tree[x += LEAF] = v;
while(x >>= 1) Tree[x] = max(Tree[x+x], Tree[x+x+1]);
}
ll get (int x, int y) {
ll ret = 0;
x += LEAF; y += LEAF;
while(x <= y) {
if((x & 1) == 1) ret = max(ret, Tree[x]);
if((y & 1) == 0) ret = max(ret, Tree[y]);
x = (x+1)>>1;
y = (y-1)>>1;
}
return ret;
}
int main() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d%d%d", X+i, G+i, D+i);
for(int i = 1; i <= N; i++) SG[i] = SG[i-1]+G[i], SD[i] = SD[i-1]+D[i], V[i] = SD[i]-X[i];
for(int i = 1; i <= N; i++) O[i] = i;
sort(O+1, O+N+1, cmpO);
for(int i = 1; i <= N; i++) update(i, SG[O[i]]), W[O[i]] = i;
for(int i = 1; i <= N; i++) {
int low = 1, high = N, p = -1;
while(low <= high) {
int mid = (low + high) >> 1;
if(SD[i-1]-X[i] <= V[O[mid]]) {
p = mid;
high = mid - 1;
}else {
low = mid + 1;
}
}
res = max(res, get(p,N) - SG[i-1]);
update(W[i], 0);
}
printf("%lld\n", res);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 3 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 4 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 5 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 6 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 7 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 8 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 9 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 10 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 11 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 12 |
Correct |
0 ms |
7188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 3 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 4 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 5 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 6 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 7 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 8 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 9 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 10 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 11 |
Correct |
0 ms |
7188 KB |
Output is correct |
| 12 |
Correct |
4 ms |
7188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
7188 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7188 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7188 KB |
Output is correct |
| 4 |
Correct |
40 ms |
7188 KB |
Output is correct |
| 5 |
Correct |
40 ms |
7188 KB |
Output is correct |
| 6 |
Correct |
84 ms |
7188 KB |
Output is correct |
| 7 |
Correct |
68 ms |
7188 KB |
Output is correct |
| 8 |
Correct |
64 ms |
7188 KB |
Output is correct |
| 9 |
Correct |
68 ms |
7188 KB |
Output is correct |
| 10 |
Correct |
76 ms |
7188 KB |
Output is correct |
| 11 |
Correct |
96 ms |
7188 KB |
Output is correct |
| 12 |
Correct |
104 ms |
7188 KB |
Output is correct |
