Submission #334598

#	Time	Username	Problem	Language	Result	Execution time	Memory
334598		sahil_k	Rice Hub (IOI11_ricehub)	C++14	100 / 100	25 ms	1900 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <cmath>
using namespace std;
bool check (int n, int pos[], long long b, int len) {
	long long total = 0;
	for (int i=0; i<len; i++) {
		total += abs(pos[i]-pos[len/2]);
	}
	if (total <= b) return true;
	for (int i=0; i<n-len; i++) {
		total -= pos[len/2+i]-pos[i];
		total += pos[i+len]-pos[len/2+i+1];
		if (len%2 == 0) total += pos[len/2+i+1]-pos[len/2+i];
		if (total <= b) return true;
	}
	return false;
}
int besthub (int n, int max_x, int pos[], long long b) {
	int o;
	int l = 1, r = n, m;
	while (l <= r) {
		m = (l+r)/2;
		bool ans = check(n, pos, b, m);
		if (ans) {
			o = m;
			l = m+1;
		} else {
			r = m-1;
		}
	}
	return o;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:32:9: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |  return o;
      |         ^

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