#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long inf = 1e9;
long long n, t[N*4];
long long h[N], sum[N], gold[N], ans;
vector<long long> coord;
int get( int x ) { return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + 1; }
void build( int l = 1, int r = coord.size(), int idx = 1 ) {
t[idx] = inf;
if( l == r ) return ;
int mid = l + r >> 1;
build( l, mid, idx<<1 ), build( mid+1, r, idx<<1|1 );
}
void update( int x, long long va, int l = 1, int r = coord.size(), int idx = 1 ) {
if( l > x || r < x ) return ;
if( l == r ) return void( t[idx] = min( t[idx], va ) );
int mid = l + r >> 1;
update( x, va, l, mid, idx<<1 ), update( x, va, mid+1, r, idx<<1|1 );
t[idx] = min( t[idx<<1], t[idx<<1|1] );
return ;
}
long long query( int ll, int rr, int l = 1, int r = coord.size(), int idx = 1 ) {
if( l > rr || r < ll ) return inf;
if( l >= ll && r <= rr ) return t[idx];
int mid = l + r >> 1;
return min( query( ll, rr, l, mid, idx<<1 ), query( ll, rr, mid+1, r, idx<<1|1 ) );
}
int main()
{
scanf("%lld",&n);
for( int i = 1 ; i <= n ; i++ ) {
scanf("%lld %lld %lld",&h[i],&gold[i],&sum[i]);
sum[i] += sum[i-1], gold[i] += gold[i-1];
coord.emplace_back( sum[i-1] - h[i] );
}
sort( coord.begin(), coord.end() );
coord.resize( unique( coord.begin(), coord.end() ) - coord.begin() );
build();
/*for( long long i : coord ) printf("%lld ",i);
printf("\n");*/
for( int i = 1 ; i <= n ; i++ ) {
int idx = upper_bound( coord.begin(), coord.end(), sum[i] - h[i] ) - coord.begin(), idx2 = get( sum[i-1] - h[i] );
update( idx2, ( long long )i );
long long qu = query( 1, idx );
//printf("%d %lld\n",i,qu);
if( qu != inf ) ans = max( ans, gold[i] - gold[qu - 1] );
}
printf("%lld",ans);
return 0;
}
Compilation message
divide.cpp: In function 'void build(int, int, int)':
divide.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
divide.cpp: In function 'void update(int, long long int, int, int, int)':
divide.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
divide.cpp: In function 'long long int query(int, int, int, int, int)':
divide.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
divide.cpp: In function 'int main()':
divide.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
divide.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&h[i],&gold[i],&sum[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
6 ms |
512 KB |
Output is correct |
| 22 |
Correct |
6 ms |
512 KB |
Output is correct |
| 23 |
Correct |
9 ms |
768 KB |
Output is correct |
| 24 |
Correct |
10 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
6 ms |
512 KB |
Output is correct |
| 22 |
Correct |
6 ms |
512 KB |
Output is correct |
| 23 |
Correct |
9 ms |
768 KB |
Output is correct |
| 24 |
Correct |
10 ms |
768 KB |
Output is correct |
| 25 |
Correct |
8 ms |
768 KB |
Output is correct |
| 26 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 27 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 28 |
Correct |
44 ms |
4080 KB |
Output is correct |
| 29 |
Correct |
47 ms |
4336 KB |
Output is correct |
| 30 |
Correct |
93 ms |
8592 KB |
Output is correct |
| 31 |
Correct |
79 ms |
7404 KB |
Output is correct |
| 32 |
Correct |
81 ms |
7532 KB |
Output is correct |
| 33 |
Correct |
83 ms |
7276 KB |
Output is correct |
| 34 |
Correct |
83 ms |
7276 KB |
Output is correct |
| 35 |
Correct |
90 ms |
7784 KB |
Output is correct |
| 36 |
Correct |
88 ms |
7912 KB |
Output is correct |
