Submission #499932

#	Time	Username	Problem	Language	Result	Execution time	Memory
499932		LittleFlowers__	Rice Hub (IOI11_ricehub)	C++17	0 / 100	1076 ms	9176 KiB

ricehub

/* input

*/

#include<bits/stdc++.h>
using namespace std;

#include "ricehub.h"

typedef long long ll;
const int N = 1e5 + 10;
int x[N], n;
ll pref[N], suff[N], k;

ll getR(int l, int r) {
	return pref[r] - pref[l - 1] - 1LL * (r - l + 1) * (x[l] - x[1]);
}

ll getL(int l, int r) {
	return suff[l] - suff[r + 1] - 1LL * (r - l + 1) * (x[n] - x[r]);
}

bool check(int mid) {
	--mid;
	int L = mid / 2, R = (mid + 1) / 2;
	for (int i = 1; i <= n; ++i) {
		if (i <= L || i + R > n) continue;
		ll val = getL(i - L, i) + getR(i, i + R);
		if(val <= k) return 1;
	}
	return 0;
}

int besthub(int nn,int lll,int xx[],long long bb){
	ll l;
n=nn,l=lll,k=bb;
	for (int i = 1; i <= n; ++i) x[i]=xx[i-1];
	sort(x + 1,  x + n + 1);

	for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + x[i] - x[1];

	for (int i = n; i; --i) suff[i] = suff[i + 1] + x[n] - x[i];

	int L = 1, R = n, res = 1;
	while (L <= R) {
		int mid = (L + R) / 2;
		if (check(mid)) {
			res = mid;
			L = mid + 1;
		}
		else R = mid - 1;
	}

	cout << res << "\n";
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:35:5: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   35 |  ll l;
      |     ^
ricehub.cpp:55:1: warning: no return statement in function returning non-void [-Wreturn-type]
   55 | }
      | ^

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