Submission #443037

#	Time	Username	Problem	Language	Result	Execution time	Memory
443037		hibye1217	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	2508 KiB

ricehub

#ifndef NOTSUBMIT
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#endif // NOTSUBMIT

typedef long long ll;

ll sum[100020];

int besthub(int R, int L, int X[], ll B){
	for (int i = 1; i <= R; i++){ sum[i] = sum[i-1] + X[i-1]; }
	int st = 1, ed = R, ans = 1;
	while (st <= ed){
		int mid = st + ed >> 1;
		ll res = 1e18;
		for (int e = mid; e <= R; e++){
			int s = e-mid+1;
			int m = s+e >> 1;
			int lc = m-s+1, rc = e-m;
			ll ls = lc*X[m-1] - (sum[m]-sum[s-1]);
			ll rs = (sum[e]-sum[m]) - rc*X[m-1];
			//cout << "RS " << sum[e] << ' ' << sum[m] << ' ' << rc << ' ' << X[m] << endl;
			//cout << "MID " << s << ' ' << m << ' ' << e << " = " << ls<<' '<<rs << endl;
			res = min(res, ls+rs);
		}
		if (res <= B){ st = mid+1; ans = mid; }
		else{ ed = mid-1; }
	}
	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:15:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int mid = st + ed >> 1;
      |             ~~~^~~~
ricehub.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |    int m = s+e >> 1;
      |            ~^~

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