Submission #854794

#	Time	Username	Problem	Language	Result	Execution time	Memory
854794		NeroZein	Divide and conquer (IZhO14_divide)	C++17	100 / 100	26 ms	6832 KiB

divide

#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;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52