제출 #1193140

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

ricehub

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

using namespace std;
ll pre_sum[100002];

ll range_sum(ll lo, ll hi) {
	if ( lo == 0) return pre_sum[hi];
	return pre_sum[hi] - pre_sum[lo - 1];
}

int besthub(int R, int L, int X[], long long B){
	int  lo, hi, dund_ind, i, can, mid, Lo, Hi, mid1, lo1, hi1, lo2, hi2, max_s;
	ll sum, s;
	for (int i = 0; i < R; i ++) {
		if ( i == 0) pre_sum[i] = X[i];
		else pre_sum[i] = pre_sum[i - 1] + X[i];
	}
	lo = 1;
	hi = R + 1;
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		can = 0;
		for (i = 0; i + mid - 1 < R; i ++) {
			dund_ind = (i + (i + mid - 1))/2;
			lo1 = i;
			hi1 = dund_ind;
			lo2 = dund_ind;
			hi2 = i + mid - 1;
			sum = 0;
			sum = sum + (hi1 - lo1 + 1) * X[dund_ind] - range_sum(lo1, hi1);
			sum = sum + range_sum(lo2, hi2) - (hi2 - lo2 + 1) * X[dund_ind];
			if (sum <= B) can = 1;
		}
//		cout << mid << " " << can << endl;
		if ( can == 1) lo = mid + 1;
		else hi = mid;
	}
	lo --;
	return lo;
}

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