제출 #1363992

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

ricehub

#include "ricehub.h"

using namespace std;

const int MAXN = 100000;

long long sp[MAXN + 1];

int besthub(int n, int lim, int x[], long long b) {
  for(int i = 0; i < n; i++) {
    sp[i + 1] = sp[i] + x[i];
  }

  int st = 1, dr = n, answer = 0;
  while(st <= dr) {
    int mij = (st + dr) / 2, ok = 0;
    for(int i = 1; i + mij - 1 <= n; i++) {
      int median = i + mij / 2;
      long long sum = 1LL * x[median - 1] * (median - i) - (sp[median - 1] - sp[i - 1]);
      sum += (sp[i + mij - 1] - sp[median]) - 1LL * x[median - 1] * (i + mij - 1 - median);
      if(sum <= b) {
        ok = 1;
      }
    }
    if(ok) {
      answer = mij;
      st = mij + 1;
    } else {
      dr = mij - 1;
    }
  }
  return answer;
}

• 서브태스크 1: 17 / 17
• 서브태스크 2: 25 / 25
• 서브태스크 3: 26 / 26
• 서브태스크 4: 32 / 32