Submission #1127380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127380		julia_08	Rice Hub (IOI11_ricehub)	C++20	100 / 100	13 ms	2376 KiB

ricehub

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

using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;

ll s[MAXN], d[MAXN];

ll cost(ll i, ll m, ll j){

  return (s[j] - s[m - 1]) - d[m] * (j - m + 1) + (m - i + 1) * d[m] - (s[m] - s[i - 1]);

}

bool p(ll s, ll r, ll b){

  if(s == 0) return true; // eh possivel
  // s = tamanho do intervalo

  // caso 1: s impar

  if(s % 2 == 1){
    for(ll k=1; k<=r; k++){
      ll i = k - (s - 1) / 2;
      ll j = k + (s - 1) / 2;

      if(i < 1 || j > r) continue;

      if(cost(i, k, j) <= b) return true;
    }

  } else{
    for(ll k=1; k<=r; k++){
      ll i = k - (s - 2) / 2 - 1;
      ll j = k + (s - 2) / 2;

      if(i < 1 || j > r) continue;

      if(cost(i, k, j) <= b) return true;

    }

    for(ll k=1; k<=r; k++){
      ll i = k - (s - 2) / 2;
      ll j = k + (s - 2) / 2 + 1;

      if(i < 1 || j > r) continue;

      if(cost(i, k, j) <= b) return true;

    }

  }

  return false;
}

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

  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";
  }

  int l_p = 0, r_p = r;

  while(l_p < r_p){

    int m = l_p + (r_p - l_p + 1) / 2;

    if(p(m, r, b)) l_p = m;
    else r_p = m - 1;

  }

  return l_p;
}

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