oj.uz

Submission #43667

# Submission time Handle Problem Language Result Execution time Memory
43667 2018-03-19T09:40:06 Z baactree Rice Hub (IOI11_ricehub) C++14
0 / 100
 43 ms 1248 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b;
int r, l, x[100005];
ll cnt[100005], sum[100005];
vector<int> xidx;
bool possi(int lcnt,int rcnt) {
	ll ret = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i < xidx.size(); i++) {
		if (cnt[i - 1] < lcnt || cnt[xidx.size() - 1] - cnt[i - 1] < rcnt)continue;
		int ridx = lower_bound(cnt, cnt + xidx.size(), cnt[i-1] + rcnt) - cnt;
		int lidx = lower_bound(cnt, cnt + xidx.size(), cnt[i-1] - lcnt) - cnt;
		lidx = max(1, lidx);
		ridx = min((int)xidx.size() - 1, ridx);
		ll now = (sum[ridx - 1] - sum[i - 1]) - (cnt[ridx - 1] - cnt[i - 1])*xidx[i];
		ll r = rcnt - (cnt[ridx - 1] - cnt[i - 1]);
		now += r * (xidx[ridx] - xidx[i]);
		now += (cnt[i - 1] - cnt[lidx-1])*xidx[i] - (sum[i - 1] - sum[lidx-1]);
		r = lcnt - (cnt[i - 1] - cnt[lidx - 1]);
		now += r * (xidx[i] - xidx[lidx-1]);
		ret = min(ret, now);
	}
	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];
		xidx.push_back(x[i]);
	}
	xidx.push_back(0);
	sort(xidx.begin(), xidx.end());
	xidx.erase(unique(xidx.begin(), xidx.end()), xidx.end());
	for (int i = 0; i < r; i++) {
		cnt[lower_bound(xidx.begin(), xidx.end(), x[i]) - xidx.begin()]++;
		sum[lower_bound(xidx.begin(), xidx.end(), x[i]) - xidx.begin()] += x[i];
	}
	for (int i = 1; i < xidx.size(); i++) {
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	int le, ri, mid, ans;
	ans = 0;
	le = 1;
	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

ricehub.cpp: In function 'bool possi(int, int)':
ricehub.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < xidx.size(); i++) {
                    ^
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < xidx.size(); i++) {
                    ^

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1248 KB Output is correct
2 Incorrect 41 ms 1248 KB Output isn't correct
3 Halted 0 ms 0 KB -