제출 #488975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488975		fun_day	쌀 창고 (IOI11_ricehub)	C++14	42 / 100	109 ms	1488 KiB

ricehub

#include <bits/stdc++.h>

using namespace std;

int besthub(int R, int L, int X[] , long long B){
  vector<long long> pref(R);
  for(int i = 0 ; i < R ; i++){
    if(i == 0) pref[i] = (long long) X[i];
    else pref[i] = pref[i - 1] + (long long) X[i];
  }
  int best = 0;
  for(int i = 1 ; i < R ; i++){
    int l = 0 , r = i;
    int ans = 0;
    while(l <= r){
      int mid = l + (r - l) / 2;
      int used = i - mid;
      long long sum = (long long) X[i] * used  - (pref[i - 1] - (mid > 0 ? pref[mid - 1] : 0));
      long long keep = B - sum;
      int left = i , right = R - 1;
      int here = 0;
      while(left <= right){
        int middle = left + (right - left) / 2;
        int cur = middle - i;
        long long s = pref[middle] - pref[i] - (long long) X[i] * cur;
        if(s + sum <= B){
          here = max(here , cur);
          left = middle + 1;
        }
        else{
          right = middle - 1;
        }
      }
      if(keep >= 0 && here + used >= ans){
        ans = max(ans , here + used);        
        r = mid - 1;
      }
      else{
        l = mid + 1;        
      }
    }
    best = max(best , ans);
    if(best == R - 1) break;
  }
  return best + 1;
}

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