Submission #1198281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198281		aykhn	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	328 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;

int check(long double a, long double x, long double b, long double y)
{
  return (a + b) * (a + b) > (a - b) * (a - b) + (x - y) * (x - y);
}
long double findr(long double x, long double b, long double y)
{
  long double l = 0, r = 1000000000;
  while (r - l > 0.000000001)
  {
    long double mid = (l + r) / 2;
    if (check(mid, x, b, y)) r = mid;
    else l = mid;
  }
  return l;
}

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);
  };
  vector<array<int, 2>> idx = {{0, 0}};
  while (1)
  {
    if (idx.back()[1] == n - 1) break;
    int ok = 0;
    for (int i = idx.back()[1] + 1; i < n; i++)
    {
      int l = idx.back()[1] + 1, r = i;
      if (sum(l, r) >= sum(idx.back()[0], idx.back()[1])) 
      {
        idx.push_back({l, r});
        ok = 1;
        break;
      }
    }
    if (!ok) break;
    for (int i = 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