Submission #1138179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138179		MattNattFeczan	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	1352 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll Inf = 1e18;

int besthub(int n, int m, int B[], ll b){
  vector<ll>A(n+2);
  A[0] = -Inf, A[n+1] = Inf;
  for(int i=0;i<n;i++){
    A[i+1] = B[i];
  }
  ll s=0,p=-1,k=1,w=0;
  for(int i=1;i<=n;i++){
    int now = A[i];
    p++, k--;
    while(s > b){
      s -= A[i]-A[i-p], p--;
    }
    while(A[i+k+1]-A[i]+s <= b || A[i+k+1] - A[i] <= A[i] - A[i-p]){
      if(A[i+k+1]-A[i]+s <= b)
        s += A[i+k+1]-A[i], k++;
      else{
        s += A[i+k+1] - A[i] - A[i] + A[i-p], p--, k++;
      }
    }
    while(A[i] - A[i-p-1] + s <= b)
      s += A[i] - A[i-p-1], p++;
    w = max(w, p+k+1);
    // cout<<p<<" "<<k<<" "<<s<<"\n";
    s += (p - k + 1) * (A[i+1] - A[i]);
  }
  return w;
}

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