Submission #585649

#	Time	Username	Problem	Language	Result	Execution time	Memory
585649		Shin	Divide and conquer (IZhO14_divide)	C++14	17 / 100	1 ms	340 KiB

divide

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct items {
  int x, g, d;
};

const int N = 1e5 + 7;
int n;
items a[N];
long long power[N];
long long gold[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i].x >> a[i].g >> a[i].d;
    power[i] = power[i - 1] + a[i].d;
    gold[i] = gold[i - 1] + a[i].g;
  }
  long long res = 0;
  for (int i = 1, j = 1; i <= n; i ++) {
    while (j <= i && a[i].x - a[j].x > power[i] - power[j - 1]) {
      j ++;
    }
    maximize(res, gold[i] - gold[j - 1]);
  }
  cout << res;
  return 0;
}

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