Submission #1129960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129960		Sofiatpc	Rice Hub (IOI11_ricehub)	C++20	17 / 100	0 ms	328 KiB

ricehub

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

using namespace std;

typedef long long ll;
const int INF = 1e9+5;

int besthub(int n, int L, int x[], ll b)
{
  ll ans = 0, r = 0, cur = 0, m = x[0], qtd = 1;

  for(int l = 0; l < n; l++){
    if(l > r){
      r = l;
      cur = 0;
      m = x[r];
      qtd = 1;
    }

    while(r < n){
      r++;

      ll nxtm;
      if((r-l+1)%2 == 1)nxtm = x[l+(r-l+1)/2];
      else nxtm = (x[l+(r-l+1)/2-1] + x[l+(r-l+1)/2])/2;

      ll nxtqtd = qtd;
      if((r-l+1)%2 == 1)nxtqtd++;

      ll nxt = cur + qtd*(nxtm-m) + abs(x[r]-m) - (r-l+1 - qtd)*(nxtm-m);

      if(nxt > b){r--; break;}

      cur = nxt; m = nxtm; qtd = nxtqtd;
    }
    
    ans = max(ans, r-l+1);

    ll nxtm;
    if((r-l)%2 == 1)nxtm = x[l+1+(r-l)/2];
    else nxtm = (x[l+1+(r-l)/2-1] + x[l+1+(r-l)/2])/2;

    ll nxtqtd = qtd;
    if((r-l)%2 == 0)nxtqtd--;

    cur = cur + qtd*(nxtm-m) - abs(x[l]-nxtm) - (r-l - (qtd-1))*(nxtm-m);
    //cerr<<" => "<<m<<" "<<nxtm<<" "<<nxtqtd<<" "<<cur<<"\n";
    m = nxtm; qtd = nxtqtd;
  }

  return ans;
}

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