Submission #979904

#	Time	Username	Problem	Language	Result	Execution time	Memory
979904		SmuggingSpun	Rice Hub (IOI11_ricehub)	C++14	0 / 100	3 ms	2652 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int cnt[lim], to_X[lim];
ll sum[lim];
int besthub(int n, int L, int X[], ll B){
	int N = 1, ans = 0;
	memset(cnt, 0, sizeof(cnt));
	memset(sum, 0, sizeof(sum));
	to_X[1] = X[0];
	for(int i = 0; i < n; i++){
		if(i > 0 && X[i] != X[i - 1]){
			to_X[++N] = X[i];
		}
		cnt[N]++;
		sum[N] += X[i];
	}
	for(int i = 1; i <= N; i++){
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	for(int i = 1; i <= N; i++){
		int low = 0, high = N, range;
		while(low <= high){
			int mid = (low + high) >> 1;
			if(1LL * to_X[i] * ((cnt[i] << 1) - cnt[max(0, i - mid - 1)] - cnt[min(N, i + mid)]) - (sum[i] << 1LL) + sum[max(0, i - mid - 1)] + sum[min(N, i + mid)] <= B){
				low = (range = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		ll remain = B - 1LL * to_X[i] * ((cnt[i] << 1) + cnt[max(0, i - range - 1)] + cnt[min(N, i + range)]) + (sum[i] << 1LL) - sum[max(0, i - range - 1)] - sum[min(N, i + range)];
		int add_cnt = 0;
		if(i - range > 1){
			int can_add = min(ll(cnt[i - range - 1]) - cnt[i - range - 2], remain / (to_X[i] - to_X[i - range - 1]));
			add_cnt += can_add;
			remain -= 1LL * can_add * (to_X[i] - to_X[i - range - 1]);
		}
		if(i + range < N){
			add_cnt += min(ll(cnt[i + range + 1]) - cnt[i + range], remain / (to_X[i + range + 1] - to_X[i]));
		}
		maximize(ans, add_cnt + cnt[min(N, i + range)] - cnt[max(0, i - range - 1)]);
	}
	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:40:94: warning: 'range' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |   ll remain = B - 1LL * to_X[i] * ((cnt[i] << 1) + cnt[max(0, i - range - 1)] + cnt[min(N, i + range)]) + (sum[i] << 1LL) - sum[max(0, i - range - 1)] - sum[min(N, i + range)];
      |                                                                                            ~~^~~~~~~

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