제출 #679028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679028		atigun	Rice Hub (IOI11_ricehub)	C++11	100 / 100	14 ms	3268 KiB

ricehub

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

int R;
ll L, B;
vector<ll> X, pf;

ll get(int l, int r){
  return pf[r]-pf[l-1];
}
ll sz(int l, int r){
  return r-l+1;
}
ll go(int l, int r){
  int mid = (l+r)/2;
  ll lsum = sz(l, mid)*X[mid]-get(l, mid);
  ll rsum = get(mid+1, r)-sz(mid+1, r)*X[mid];
  return lsum+rsum;
}

int besthub(int rr, int ll, int xx[], long long bb){
  R = rr, L = ll, B = bb;
  X.resize(R+5);
  for(int i = 1; i <= R; i++)
    X[i] = xx[i-1];
  pf = X;
  for(int i = 1; i <= R; i++)
    pf[i]+= pf[i-1];
  int left = 1, right = 1;
  int ans = 0;
  while(left <= R){
    while(right+1 <= R && go(left, right+1) <= B)
      right++;
    ans = max(ans, right-left+1);
    left++;
  }
  return ans;
}

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