Submission #1202723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202723		aykhn	Divide and conquer (IZhO14_divide)	C++20	100 / 100	56 ms	6088 KiB

divide

#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--)
  {
    sg += g[i], sd += d[i];
    v1.push_back({x[mid] - x[i] - sd, sg});
  }
  for (int i = mid + 1, sg = 0, sd = 0; i <= r; i++)
  {
    sg += g[i], sd += d[i];
    v2.push_back({x[i] - x[mid] - sd, sg});
  }
  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';
}

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