제출 #854794

#제출 시각아이디문제언어결과실행 시간메모리
854794NeroZein금 캐기 (IZhO14_divide)C++17
100 / 100
26 ms6832 KiB
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> x(n + 1), g(n + 1), d(n + 1); 
  for (int i = 1; i <= n; ++i) {
    cin >> x[i] >> g[i] >> d[i];
  }
  vector<long long> pg(n + 1); 
  for (int i = 1; i <= n; ++i) {
    pg[i] = pg[i - 1] + g[i]; 
  }
  vector<long long> ps(n + 1); 
  for (int i = 1; i <= n; ++i) {
    ps[i] = ps[i - 1] + d[i]; 
  }
  vector<long long> suf(n + 1); 
  suf[n] = x[n] - ps[n];
  for (int i = n - 1; i > 0; --i) {
    suf[i] = min(suf[i + 1], x[i] - ps[i]); 
  }
  long long ans = 0; 
  for (int i = 1; i <= n; ++i) {
    long long key = x[i] - ps[i - 1];
    int l = i, r = n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (suf[mid] <= key) {
        l = mid;
      } else {
        r = mid - 1; 
      }
    }
    ans = max(ans, pg[l] - pg[i - 1]); 
  }
  cout << ans << '\n'; 
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...