This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define str string
#define pb push_back
#define pf push_front
#define nl "\n"
#define ll long long
#define int long long
#define all(v) (v).begin() , (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
#define len(a) a.size()
#define pii pair<int,int>
const int N = 3e6 + 1;
const ll md = 998244353;
const ll mod = 1e9 + 7;
const ll mega = 1e6 + 3;
const ll inf = 100100;
int x[N] , g[N] , d[N] , pref[N] , pref2[N] ,n , ans , mx;
void add(int l){
ans += d[l];
}
void del(int l){
ans -= d[l];
}
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> x[i] >> g[i] >> d[i];
pref[i] = pref[i - 1] + d[i];
pref2[i] = pref2[i - 1] + g[i];
}
int mx = 0;
if(n <= 100){
for(int i = 1; i <= n; ++i){
for(int j = i; j <= n; ++j){
if(x[j] - x[i] <= pref[j] - pref[i - 1]){
mx = max(mx , pref2[j] - pref2[i - 1]);
}
}
}
cout << mx;
}
else if(n <= 5000){
for(int i = 1; i <= n; ++i){
int l = i , r = n;
while(l <= r){
int m = (l + r) / 2;
if(pref[m] - pref[i - 1] >= x[m] - x[i]){
l = m + 1;
mx = max(mx , pref2[m] - pref2[i - 1]);
}
else{
r = m - 1;
}
}
}
cout << mx;
}
}
signed main() {
SPEED;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
// #ifndef ONLINE_JUDGE
// cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
// #endif
// return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |