Submission #392620

#	Time	Username	Problem	Language	Result	Execution time	Memory
392620		ritul_kr_singh	Rice Hub (IOI11_ricehub)	C++17	100 / 100	30 ms	2520 KiB

ricehub

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

int besthub(int n, int L, int X[], ll B){
	ll pre[n+1] = {0};
	for(int i=0; i<n; ++i) pre[i+1] = (ll)X[i] + pre[i];
	int ans = 1;

	for(int i=1; i<=n; ++i){
		int low = i, high = n;
		while(low < high){
			int mid = (low + high) / 2;
			++mid;

			int mx = (mid + i) / 2;
			ll cost = 0, pos = X[mx - 1];
			if(i < mx){
				ll s = pre[mx-1] - pre[i-1];
				cost += pos * (mx - i) - s;
			}
			if(mx < mid){
				ll s = pre[mid] - pre[mx];
				cost += s - pos * (mid - mx);
			}
			if(cost <= B) low = mid;
			else high = mid - 1;
		}
		ans = max(ans, low - i + 1);
	}
	return ans;
}

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