#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 upper_bound( coord.begin(), coord.end(), x ) - coord.begin(); }
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 = get( sum[i] - h[i] ), idx2 = get( sum[i-1] - h[i] );
update( idx2, ( long long )i );
long long qu = query( 1, idx );
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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 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 |
304 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 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 |
304 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 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 |
6 ms |
384 KB |
Output is correct |
| 18 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 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 |
304 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 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 |
6 ms |
384 KB |
Output is correct |
| 18 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
