Submission #1198299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198299		aykhn	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	320 KiB

segments

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 3e3 + 5;
const int mod = 1e9 + 7;


void _()
{
  int n;
  cin >> n;
  int a[n], p[n];
  for (int &i : a) cin >> i;
  for (int i = 0; i < n; i++) p[i] = (i ? p[i - 1] : 0) + a[i];
  auto sum = [&](int l, int r)
  {
    if (l > r) return 0LL;
    return p[r] - (l ? p[l - 1] : 0LL);
  };
  auto findmid = [&](int l, int r)
  {
    int lx = l, rx = r;
    while (lx < rx)
    {
      int mid = (lx + rx + 1) >> 1;
      if (sum(l, mid - 1) <= sum(mid, r)) lx = mid;
      else rx = mid - 1;
    }
    return lx;
  };
  vector<array<int, 2>> idx = {{0, 0}};
  while (1)
  {
    if (idx.back()[1] == n - 1) break;
    int sz = idx.size();
    idx.back()[1]++;
    int m = findmid(idx.back()[0], idx.back()[1]);
    if (m > idx.back()[0] && sum(idx[sz - 2][0], idx[sz - 2][1]) <= sum(idx.back()[0], m - 1))
    {
      idx.push_back({m, idx.back()[1]});
      idx[(int)idx.size() - 2][1] = m - 1;
    }
    else continue;
    for (int i = (int)idx.size() - 1; i > 0; i--)
    {
      while (sum(idx[i - 1][0], idx[i - 1][1] + 1) <= sum(idx[i][0] + 1, idx[i][1])) idx[i - 1][1]++, idx[i][0]++;
    }
  }
  cout << idx.size() << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27