Submission #79068

#	Time	Username	Problem	Language	Result	Execution time	Memory
79068		Plurm	Rice Hub (IOI11_ricehub)	C++11	0 / 100	7 ms	852 KiB

ricehub

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

int besthub(int R, int L, int X[], long long B)
{
	int lo = 0;
	int hi = R;
	int mid;
	deque<int> dq;
	deque<long long> qs;
	long long QS[R];
	QS[0] = X[0];
	for(int i = 1; i < R; i++){
		QS[i] = QS[i-1] + (long long)X[i];
	}
	while(lo < hi){
		mid = (lo + hi + 1)/2;
		dq.clear();
		qs.clear();
		for(int i = 0; i < mid; i++){
			dq.push_back(X[i]);
			qs.push_back(QS[i]);
		}
		long long s = qs[mid-1] - qs[mid/2] - (long long)(mid-mid/2-1)*dq[mid/2] +
			(long long)(mid/2)*dq[mid/2] - qs[mid/2-1];
		for(int i = mid; i < R; i++){
			dq.pop_front();
			qs.pop_front();
			dq.push_back(X[i]);
			qs.push_back(QS[i]);
			s = min(s,qs[mid-1] - qs[mid/2] - (long long)(mid-mid/2-1)*dq[mid/2] +
					(long long)(mid/2)*dq[mid/2] - qs[mid/2-1]);
		}
		if(s <= B){
			lo = mid;
		}else{
			hi = mid-1;
		}
	}
	return lo;
}

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