oj.uz

Submission #79066

# Submission time Handle Problem Language Result Execution time Memory
79066 2018-10-11T02:45:46 Z Plurm Rice Hub (IOI11_ricehub) C++11
0 / 100
 1000 ms 1264 KB 
#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)/2;
		dq.clear();
		qs.clear();
		for(int i = 0; i < mid; i++){
			dq.push_back(X[i]);
			qs.push_back(QS[i]);
		}
		int x = dq[mid/2];
		long long s = qs[mid-1] - qs[mid/2] - (long long)(mid-mid/2-1)*x +
			(long long)(mid/2)*x - 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)*x +
					(long long)(mid/2)*x - qs[mid/2-1]);
		}
		if(s <= B){
			lo = mid;
		}else{
			hi = mid-1;
		}
	}
	return lo;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1264 KB Output isn't correct
2 Halted 0 ms 0 KB -