oj.uz

Submission #499932

# Submission time Handle Problem Language Result Execution time Memory
499932 2021-12-30T04:56:58 Z LittleFlowers__ Rice Hub (IOI11_ricehub) C++17
0 / 100
 1000 ms 9176 KB 
/* 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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 9076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 9092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 9176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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