제출 #1318433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318433		muramasa	쌀 창고 (IOI11_ricehub)	C++20	100 / 100	8 ms	1080 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,a[1000005];
ll k;

bool ch(int m){
  ll suml = 0,sumr = 0;
  for(int i = 0;i < (m - 1)/2;i++) suml += a[i];
  for(int i = (m + 1)/2;i < m;i++) sumr += a[i];
  if((1LL * (m - 1)/2 * a[(m - 1)/2] - suml) + (sumr - (1LL * m/2 * a[(m - 1)/2])) <= k)return 1;
  for(int i = m;i < n;i++){
    suml -= a[i - m];
    suml += a[(m - 1)/2 + i - m];
    sumr -= a[(m - 1)/2 + i - m + 1];
    sumr += a[i];
    if((1LL * (m - 1)/2 * a[(m - 1)/2 + i - m + 1] - suml) + (sumr - (1LL * m/2 * a[(m - 1)/2 + i - m + 1])) <= k)return 1;
  }
  // cout << endl;
  return 0;
}

int besthub(int R, int L, int X[], long long B)
{
  n = R;
  k = B;
  for(int i = 0;i < n;i++)a[i] = X[i];
  int l = 2,r = n,ans = 1;
  // ch(3);
  while(l <= r){
    int m = (l+r)/2;
    if(ch(m)){
      l = m + 1;
      ans = m;
    }else{
      r = m - 1;
    }
  }
  return ans;
}

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