Submission #1127372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127372		julia_08	Rice Hub (IOI11_ricehub)	C++20	68 / 100	787 ms	900 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 5e3 + 10;

ll s[MAXN];

int besthub(int r, int l, int x[], ll b){

  vector<ll> val(r + 1), d(r + 1);

  for(int i=1; i<=r; i++){
    d[i] = (ll) x[i - 1];
  }

  for(int i=1; i<=r; i++){
    s[i] = s[i - 1] + d[i];
    // cout << i << " " << s[i] << "\n";
  }

  ll ans = 0;

  for(ll i=1; i<=r; i++){

    for(ll j=i; j<=r; j++){

      ll m1 = (i + j) / 2, m2 = m1 + 1;

      ll cost_1 = 1e18, cost_2 = 1e18;

      if(i <= m1 && m1 <= j) cost_1 = ((s[j] - s[m1 - 1]) - (j - m1 + 1) * d[m1]) + ((m1 - i + 1) * d[m1] - (s[m1] - s[i - 1]));
      if(i <= m2 && m2 <= j) cost_2 = ((s[j] - s[m2 - 1]) - (j - m2 + 1) * d[m2]) + ((m2 - i + 1) * d[m2] - (s[m2] - s[i - 1]));

      if(cost_1 <= b || cost_2 <= b) ans = max(ans, j - i + 1);

    }
  }

  return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32