oj.uz

Submission #255258

# Submission time Handle Problem Language Result Execution time Memory
255258 2020-07-31T16:33:31 Z tuna Divide and conquer (IZhO14_divide) C++11
0 / 100
 0 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5, M = 2e14;

int n;
ll x[N], g[N], d[N];

map<ll, ll> tree;

void upd(ll k, ll x) {
  while (k < M) {
    if (tree.find(k) == tree.end()) {
      tree[k] = x;
    } else {
      tree[k] = min(tree[k], x);
    }
    k += k & -k;
  }
}

ll que(ll k) {
  ll ans = LLONG_MAX;
  while (k) {
    if (tree.find(k) != tree.end()) {
      ans = min(ans, tree[k]);
    }
    k -= k & -k;
  }
  return ans;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> g[i] >> d[i];
    d[i] += d[i - 1];
    g[i] += g[i - 1];
  }
  ll ans = 0;
  upd(M / 2, 0);
  for (int i = 1; i <= n; i++) {
    ans = max(ans, g[i] - g[i - 1]);
    ans = max(ans, g[i] - que(d[i] - x[i] + M / 2));
    upd(d[i] - x[i] + M / 2, g[i]);
  }
  cout << ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -