제출 #990147

#제출 시각아이디문제언어결과실행 시간메모리
990147tch1cherinDivide and conquer (IZhO14_divide)C++17
100 / 100
51 ms11348 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> x(N), g(N), d(N);
  for (int i = 0; i < N; i++) {
    cin >> x[i] >> g[i] >> d[i];
  }
  vector<long long> pref_d(N + 1), pref_g(N + 1);
  for (int i = 0; i < N; i++) {
    pref_d[i + 1] = pref_d[i] + d[i];
    pref_g[i + 1] = pref_g[i] + g[i];
  }
  set<pair<long long, long long>> S;
  long long answer = 0;
  for (int i = 0; i < N; i++) {
    auto it = S.lower_bound({pref_d[i] - x[i], numeric_limits<int>::max()});
    bool good = true;
    if (it != S.begin()) {
      if (prev(it)->second < pref_g[i]) {
        good = false;
      }
    }
    if (good) {
      while (it != S.end() && it->second >= pref_g[i]) {
        it = S.erase(it);
      }
      S.insert({pref_d[i] - x[i], pref_g[i]});
    }
    it = S.lower_bound({pref_d[i + 1] - x[i], numeric_limits<int>::max()});
    assert(it != S.begin());
    answer = max(answer, pref_g[i + 1] - prev(it)->second);
  }
  cout << answer << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...