Submission #334538

#	Time	Username	Problem	Language	Result	Execution time	Memory
334538		Pety	Divide and conquer (IZhO14_divide)	C++14	100 / 100	127 ms	5996 KiB

divide

#include <bits/stdc++.h>

using namespace std;

int n;
int x[100002];
long long g[100002], d[100002], mn[100002];

int cb (int i, long long val) {
  int st = 1, dr = i, ans;
  while (st <= dr) {
    int mij = (st + dr) / 2;
    if (mn[mij] <= val) {
      dr = mij - 1;
      ans = mij;
    }
    else
      st = mij + 1;
  }
  return ans;
}

int main()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> x[i] >> g[i] >> d[i];
  long long ans = 0;
  mn[0] = 1e18;
  for (int i = 1; i  <= n; i++) {
    g[i] += g[i - 1];
    d[i] += d[i - 1];
    mn[i] = min(d[i - 1] - x[i], mn[i - 1]);
    int poz = cb(i, d[i] - x[i]);
    ans = max(ans, g[i] - g[poz - 1]);
  }
  ///sum[i] - sum[j - 1] - x[i] + x[j] >= 0
  ///sum[i] - x[i] >= sum[j - 1] - x[j]
  cout << ans;
  return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int cb(int, long long int)':
divide.cpp:20:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |   return ans;
      |          ^~~
divide.cpp: In function 'int main()':
divide.cpp:35:33: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     ans = max(ans, g[i] - g[poz - 1]);
      |                             ~~~~^~~

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