fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define llong long long
  4.  
  5. #define F first
  6. #define S second
  7.  
  8. #define pb push_back
  9. #define mp make_pair
  10.  
  11. using namespace std;
  12.  
  13. const int INF = (int) 1e9 + 7;
  14. const int MXN = (int) 2e5 + 7;
  15.  
  16. struct node {
  17.     int pos, g, e;
  18. };
  19.  
  20. int n;
  21. int smax[MXN];
  22.  
  23. llong ans;
  24. llong sg[MXN], se[MXN];
  25.  
  26. node a[MXN];
  27. pair<llong, int> all[MXN];
  28.  
  29. int main() {
  30.     freopen("divide.in", "r", stdin);
  31.     freopen("divide.out", "w", stdout);
  32.  
  33.     scanf("%d", &n);
  34.     for (int i = 1; i <= n; i++) {
  35.         scanf("%d%d%d", &a[i].pos, &a[i].g, &a[i].e);
  36.  
  37.         sg[i] = sg[i - 1] + a[i].g;
  38.         se[i] = se[i - 1] + a[i].e;
  39.  
  40.         all[i] = mp(se[i] - a[i].pos, i);
  41.     }
  42.     sort(all + 1, all + n + 1);
  43.     for (int i = n; i >= 1; i--)
  44.         smax[i] = max(smax[i + 1], all[i].S);
  45.  
  46.     for (int i = 1; i <= n; i++) {
  47.         int low = lower_bound(all + 1, all + n + 1, mp(se[i - 1] - a[i].pos, 0)) - all;
  48.         int nxt = smax[low];
  49.         ans = max(ans, sg[nxt] - sg[i - 1]);
  50.     }
  51.     cout << ans;
  52.     return 0;
  53. }
Success #stdin #stdout 0s 24608KB
comments (?)
stdin
copy 
4
0 5 1
1 7 2
4 4 1
7 15 1
stdout
copy 
Standard output is empty
https://ideone.com/r2xQIl
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!