Submission #43673

#	Time	Username	Problem	Language	Result	Execution time	Memory
43673		baactree	Rice Hub (IOI11_ricehub)	C++14	100 / 100	39 ms	2000 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b;
int r, l, x[100005];
bool possi(ll lcnt,ll rcnt) {
	ll ret = 0x3f3f3f3f3f3f3f3f;
	deque<int> le, ri;
	ll sum = 0;
	for (int i = 0; i < r; i++) {
		if (le.size() < lcnt) {
			le.push_back(i);
			sum -= x[i];
		}
		else if (ri.size() < rcnt) {
			ri.push_back(i);
			sum += x[i];
		}
		else {
			sum += x[le.front()];
			le.pop_front();
			sum -= x[ri.front()];
			sum -= x[ri.front()];
			le.push_back(ri.front());
			ri.pop_front();
			ri.push_back(i);
			sum += x[i];
		}
		if (le.size() == lcnt && ri.size() == rcnt) {
			ret = min(ret, sum + lcnt * x[ri.front()] - rcnt * x[ri.front()]);
		}
	}
	return ret <= b;
}
int besthub(int R, int L, int X[], long long B)
{
	r = R; l = L; b = B;
	for (int i = 0; i < r; i++) 
		x[i] = X[i];
	sort(x, x + r);
	int le, ri, mid, ans;
	ans = 1;
	le = 2;
	ri = r;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (possi(mid/2,mid-mid/2)) {
			ans = mid;
			le = mid + 1;
		}
		else
			ri = mid - 1;
	}
	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'bool possi(ll, ll)':
ricehub.cpp:12:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (le.size() < lcnt) {
                 ^
ricehub.cpp:16:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (ri.size() < rcnt) {
                      ^
ricehub.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (le.size() == lcnt && ri.size() == rcnt) {
                 ^
ricehub.cpp:30:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (le.size() == lcnt && ri.size() == rcnt) {
                                      ^

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