Submission #1092096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092096		juicy	Divide and conquer (IZhO14_divide)	C++17	100 / 100	60 ms	8816 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  const long long inf = 1e18;

  int n; cin >> n;
  set<array<long long, 2>> st;
  auto qry = [&](long long x) {
    auto it = st.upper_bound({x + 1, -inf});
    return it == st.begin() ? inf : (*prev(it))[1];
  };
  auto add = [&](long long x, long long y) {
    if (qry(x) <= y) {
      return;
    }
    auto it = st.insert({x, y}).first;
    for (++it; it != st.end(); it = st.erase(it)) {
      if ((*it)[1] < y) {
        break;
      }
    }
  };
  long long x = 0, y = 0, res = 0;
  while (n--) {
    int p, g, d; cin >> p >> g >> d;
    add(y - p, x);
    x += g, y += d;
    res = max(res, x - qry(y - p));
  }
  cout << res;
  return 0;
}

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