Submission #676134

#	Time	Username	Problem	Language	Result	Execution time	Memory
676134		esomer	Rice Hub (IOI11_ricehub)	C++17	100 / 100	34 ms	7704 KiB

ricehub

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;

int findright(int val, vector<int>& v){
	int lo = 0;
	int hi = (int)v.size() - 1;
	int bst;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(v[mid] <= val){
			bst = mid;
			lo = mid + 1;
		}else hi = mid - 1;
	}
	return bst;
}

int findleft(int val, vector<int>& v){
	int lo = 0;
	int hi = (int)v.size() - 1;
	int bst;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(v[mid] >= val){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	return bst;
}

int besthub(int R, int L, int* X, long long B){
	vector<ll> prefix(R);
	vector<int> v(R);
	for(int i = 0; i < R; i++) v[i] = X[i];
	prefix[0] = X[0];
	map<int, int> m;
	m[X[0]]++;
	for(int i = 1; i < R; i++){
		prefix[i] = prefix[i - 1] + X[i];
		m[X[i]]++;
	}
	int ans = 0;
	int l = 0;
	int r = 0;
	while(r < R){
		int i = l + (r - l + 1) / 2;
		int right = r;
		int left = l;
		ll trucksr = right - i;
		ll trucksl = i - left;
		ll ind = X[i];
		ll cost = prefix[right] - prefix[i] - (trucksr * ind);
		ll x = 0;
		if(left > 0) x = prefix[left - 1];
		cost += ((trucksl + 1) * ind) - (prefix[i] - x);
		if(cost > B){
			l++;
			continue;
		}
		int trucks = trucksr + trucksl + 1;
		ans = max(ans, trucks);
		r++;
	}
	//~ for(int i = 0; i < R; i++){
		//~ if(m[X[i]] > ans){
			//~ ans = m[X[i]];
			//~ pl = X[i];
		//~ }
		//~ ll lo = 1;
		//~ ll hi = L;
		//~ while(lo <= hi){
			//~ ll mid = (lo + hi) / 2;
			//~ int right = findright(X[i] + mid - 1, v);
			//~ int left = findleft(X[i] - mid + 1, v);
			//~ ll trucksr = right - i;
			//~ ll trucksl = i - left;
			//~ ll ind = X[i];
			//~ ll cost = prefix[right] - prefix[i] - (trucksr * ind);
			//~ ll x = 0;
			//~ if(left > 0) x = prefix[left - 1];
			//~ cost += ((trucksl + 1) * ind) - (prefix[i] - x);
			//~ if(cost > B){
				//~ hi = mid - 1;
				//~ continue;
			//~ }
			//~ int trucks = trucksr + trucksl + 1 + min((B - cost) / mid, (ll)(m[X[i] + mid] + m[X[i] - mid]));
			//~ if(trucks > ans){
				//~ ans = trucks;
				//~ pl = X[i];
			//~ }
			//~ lo = mid + 1;
		//~ }
	//~ }
	return ans;
}
 
//~ signed main(){
    //~ ios_base::sync_with_stdio(0);
    //~ cin.tie(0);

    //~ //freopen("inpt.txt", "r", stdin);
    //~ //freopen("out.txt", "w", stdout);
	
    //~ int tt; cin >> tt;
    //~ //int tt = 1;
    //~ for(int t = 1; t <= tt; t++){
        //~ solve();
    //~ }
//~ }

Compilation message (stderr)

ricehub.cpp: In function 'int findright(int, std::vector<int>&)':
ricehub.cpp:21:9: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |  return bst;
      |         ^~~
ricehub.cpp: In function 'int findleft(int, std::vector<int>&)':
ricehub.cpp:35:9: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |  return bst;
      |         ^~~

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