Submission #676134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
676134	2022-12-29T12:16:02 Z	esomer	Rice Hub (IOI11_ricehub)	C++17	100 / 100	34 ms	7704 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	312 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	308 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	308 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	312 KB	Output is correct
16	Correct	1 ms	312 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	312 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	596 KB	Output is correct
24	Correct	2 ms	580 KB	Output is correct
25	Correct	2 ms	596 KB	Output is correct
26	Correct	2 ms	584 KB	Output is correct
27	Correct	2 ms	596 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct

Subtask #4
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1584 KB	Output is correct
2	Correct	5 ms	1576 KB	Output is correct
3	Correct	28 ms	7532 KB	Output is correct
4	Correct	29 ms	7628 KB	Output is correct
5	Correct	6 ms	1492 KB	Output is correct
6	Correct	6 ms	1492 KB	Output is correct
7	Correct	13 ms	2884 KB	Output is correct
8	Correct	13 ms	2900 KB	Output is correct
9	Correct	8 ms	1836 KB	Output is correct
10	Correct	9 ms	1732 KB	Output is correct
11	Correct	31 ms	7704 KB	Output is correct
12	Correct	31 ms	7568 KB	Output is correct
13	Correct	13 ms	3704 KB	Output is correct
14	Correct	14 ms	3760 KB	Output is correct
15	Correct	21 ms	5652 KB	Output is correct
16	Correct	21 ms	5620 KB	Output is correct
17	Correct	25 ms	6824 KB	Output is correct
18	Correct	27 ms	6840 KB	Output is correct
19	Correct	27 ms	7208 KB	Output is correct
20	Correct	34 ms	7244 KB	Output is correct

Submission #676134

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 25.0 / 25.0

Subtask #3 26.0 / 26.0

Subtask #4 32.0 / 32.0

Subtask #1
17.0 / 17.0

Subtask #2
25.0 / 25.0

Subtask #3
26.0 / 26.0

Subtask #4
32.0 / 32.0