Submission #346310

#	Time	Username	Problem	Language	Result	Execution time	Memory
346310		Mefarnis	Rice Hub (IOI11_ricehub)	C++14	0 / 100	3 ms	620 KiB

ricehub

#include <algorithm>
#include "ricehub.h"
using namespace std;

long long getCost(int l , int r , int x[], long long sum[]) {
	int m = (l+r) >> 1;
	long long cost = 0;
	if(l < m)
		cost += (m-l) * (long long) x[m] - (sum[m-1] - sum[l-1]);
	if(m < r)
		cost += (sum[r] - sum[m]) - (r-m) * (long long) x[m];
	return cost;
}

int besthub(int n, int xmax, int x[], long long budget)
{
	int ans = 0;
	long long sum[n+1];
	sum[0] = 0;
	for( int i = 1 ; i <= n ; i++ )
		sum[i] = sum[i-1] + x[i-1];
	for( int l = 1 , r = 1 ; l <= n ; l++ ) {
		r = max(l,r);
		while(r < n && getCost(l,r,x,sum) <= budget)
			r++;
		ans = max(ans,r-l+1);
	}
	return ans;
}

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