제출 #1195070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195070		SonicML	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	2376 KiB

ricehub

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

using namespace std;

typedef long long ll;

int const NMAX = 1e5;
ll arr[1 + NMAX];
ll presum[1 + NMAX];

ll computeCost(int from, int to) {
  int mid = (from + to) / 2;
  ll mult1 = mid-from+1, mult2 = to-mid;
  ll half1 = presum[mid] - presum[from-1], half2 = presum[to] - presum[mid]; 
  ll cost1 = mult1 * arr[mid] - half1, cost2 = half2 - mult2 * arr[mid];
  return cost1 + cost2;
}

int besthub(int R, int L, int X[], long long B) {
  int n = R;
  for(int i = 1;i <= n;i++) {
    arr[i] = X[i-1];
    presum[i] = presum[i-1] + X[i-1];
  }
  int ans = 0; 
  int from = 1;
  for(int to = 1;to <= n;to++) {
    ll cost = computeCost(from, to);
    while(cost > B) {
      from++;
      cost = computeCost(from, to);
    }
    ans = max(ans, to - from + 1);
  }
  return ans;
}

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