Submission #685108

#	Time	Username	Problem	Language	Result	Execution time	Memory
685108		cadmiumsky	Rice Hub (IOI11_ricehub)	C++14	100 / 100	373 ms	2968 KiB

ricehub

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

using namespace std;

using ll = long long;
//#define int ll 

#define sz(x) (x).size()
namespace {

  const int nmax = 1e5 + 5;
  const ll inf = 2e15 + 10;
  const double A = 0.38196601125, B = 1 - A;

  using pii = pair<int,int>;
  using tii = tuple<int,int,int>;
  using tiii = tuple<int,int,int,ll>;

  int n;
  int X[nmax];
  ll sum[nmax];

  #define sum (sum + 1)

}

ll get(int l, int mid, int r) {
  int ptrr = upper_bound(X, X + n, mid) - X;
  int ptrl = ptrr - 1;
  return (ll)(ptrl - l + 1) * mid - (sum[ptrl] - sum[l - 1]) + (sum[r] - sum[ptrr - 1]) - (ll)(r - ptrr + 1) * mid;
}

ll get(int l, int r) {
  if(l >= n || r >= n) return inf;
  int cl = X[l], cr = X[r];
  int ccl = B * (double)cl + A * (double)cr;
  int ccr = A * (double)cl + B * (double)cr;
  ll vl = get(l, ccl, r), vr = get(l, ccr, r);
  
  while(cr - cl > 4) {
    if(vl > vr) {
      cl = ccl;
      vl = vr;
      ccl = ccr;
      ccr = A * (double)cl + B * (double)cr;
      vr = get(l, ccr, r);
    }
    else {
      cr = ccr;
      vr = vl;
      ccr = ccl;
      ccl = B * (double)cl + A * (double)cr;
      vl = get(l, ccl, r);
    }
  } 
  
  
  ll mn = get(l, cl, r);
  for(int i = cl + 1; i <= cr; i++)
    mn = min(mn, get(l, i, r));
  return mn;
}

int besthub(int N, int vmx, int XX[], long long lim) {
  { // rename
    n = N;
    for(int j = 0; j < n; j++)  
      X[j] = XX[j];
  }
  { // spart
    for(int i = 0; i < n; i++) {
      sum[i] = sum[i - 1] + X[i];
    }
    sum[n] = sum[n - 1];
    sum[n + 1] = sum[n - 1];
  }
  
  int r = 0;
  int mx = 0;
  for(int l = 0; l < n; l++) {
    r = max(l, r);
    while(get(l, r) <= lim)
      r++;
    r--;
    mx = max(mx, r - l + 1);
  }
  return mx;
}

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