Submission #1202735

#TimeUsernameProblemLanguageResultExecution timeMemory
1202735aykhnDivide and conquer (IZhO14_divide)C++20
100 / 100
55 ms5948 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 5e5 + 5;

int n;
int x[MXN], g[MXN], d[MXN];

int f(int l, int r)
{
  if (l > r) return -inf;
  int mid = (l + r) >> 1;
  vector<array<int, 2>> v1 = {{0, 0}}, v2 = {{0, 0}};
  for (int i = mid - 1, sg = 0, sd = 0; i >= l; i--) v1.push_back({x[mid] - x[i] - (sd += d[i]), sg += g[i]});
  for (int i = mid + 1, sg = 0, sd = 0; i <= r; i++) v2.push_back({x[i] - x[mid] - (sd += d[i]), sg += g[i]});
  sort(v1.begin(), v1.end()), sort(v2.rbegin(), v2.rend());
  int res = 0;
  for (int i = 0, j = 0, mx = -inf; i < v2.size(); i++)
  {
    while (j < v1.size() && v1[j][0] + v2[i][0] <= d[mid]) mx = max(mx, v1[j][1]), j++;
    res = max(res, mx + v2[i][1] + g[mid]);
  }
  return max({res, f(l, mid - 1), f(mid + 1, r)});
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x[i] >> g[i] >> d[i];
  cout << f(0, n - 1) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...