Submission #1127358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127358		julia_08	Rice Hub (IOI11_ricehub)	C++20	0 / 100	1 ms	328 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);

  for(int i=r-1; i>=0; i--){
    x[i + 1] = x[i];
  }

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

  int ans = 0;

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

    val[0] = -1e18;

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

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

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

      int 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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32