oj.uz

Submission #43668

# Submission time Handle Problem Language Result Execution time Memory
43668 2018-03-19T09:45:13 Z baactree Rice Hub (IOI11_ricehub) C++14
17 / 100
 57 ms 3460 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;
		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])*xidx[i] - (sum[i - 1] - sum[lidx]);
		r = lcnt - (cnt[i - 1] - cnt[lidx]);
		now += r * (xidx[i] - xidx[lidx]);
		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:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < xidx.size(); i++) {
                    ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Incorrect 1 ms 644 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Incorrect 2 ms 644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1260 KB Output is correct
2 Correct 46 ms 1260 KB Output is correct
3 Correct 57 ms 3460 KB Output is correct
4 Correct 56 ms 3460 KB Output is correct
5 Incorrect 25 ms 3460 KB Output isn't correct
6 Halted 0 ms 0 KB -