Submission #337538

#	Time	Username	Problem	Language	Result	Execution time	Memory
337538		boykut	Divide and conquer (IZhO14_divide)	C++14	100 / 100	37 ms	5100 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define MAXN 100100

int x[MAXN], g[MAXN], d[MAXN], n;
int prg[MAXN], prd[MAXN], mn[MAXN];
int ans;

int search(int i, int E) {
   int l = 1, r = i, pos = 1;
   while (l < r) {
      int m = (l + r) / 2;
      if (mn[m] <= E) {
         r = m;
      } else {
         l = m + 1;
      }
   }
   return r;
}

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   cin >> n;
   
   for (int i = 1; i <= n; i++) {
      cin >> x[i] >> g[i] >> d[i];
   }
   
   mn[0] = 1e18;
   for (int i = 1; i <= n; i++) {
      prg[i] = g[i];
      prd[i] = d[i];
      prg[i] += prg[i - 1],
      prd[i] += prd[i - 1];
      mn[i] = min(mn[i - 1], prd[i - 1] - x[i]);
      
      int left = search(i, prd[i] - x[i]);
      ans = max(ans, prg[i] - prg[left - 1]);
   }
   
   cout << ans << '\n';
   
   return 0;
}

Compilation message (stderr)

divide.cpp: In function 'long long int search(long long int, long long int)':
divide.cpp:13:22: warning: unused variable 'pos' [-Wunused-variable]
   13 |    int l = 1, r = i, pos = 1;
      |                      ^~~

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