Submission #1127370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127370		julia_08	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1096 ms	836 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++){

    val[0] = -1e18;

    for(ll j=1; j<=r; j++){
      val[j] = -(s[j - 1] - j * d[i]);
    }

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

      ll cost = (s[j] - s[i - 1]) - d[i] * (j - i + 1) + (i + 1) * d[i] - s[i];

      ll pos = lower_bound(val.begin(), val.end(), cost - b) - val.begin();

      // cout << i << " " << j << " " << pos << "\n";

      if(pos <= 0) continue;

      ans = max(ans, j - pos + 1);

    }
  }

  return ans;
}

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