Submission #345071

#	Time	Username	Problem	Language	Result	Execution time	Memory
345071		Kevin_Zhang_TW	Rice Hub (IOI11_ricehub)	C++17	100 / 100	21 ms	2924 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 59;
int n, x[MAX_N];
ll pf[MAX_N];

ll cost(int wid) {
	ll res = inf;
	for (int i = 1;i + wid - 1 <= n;++i) {
		int mid = i + wid / 2;

		ll fr = pf[mid-1] - pf[i-1], ba = pf[i+wid-1] - pf[mid];
		ll fcnt = mid - i, bcnt = i + wid - 1 - mid;
		chmin(res, 1ll * x[mid] * (fcnt - bcnt) - fr + ba);
	}
	return res;
}
int besthub(int N, int _, int X[], long long B) {
	n = N;
	for (int i = 0;i < n;++i)
		x[i+1] = X[i];
	for (int i = 1;i <= n;++i)
		pf[i] = pf[i-1] + x[i];

	int L = 0, R = N, M;
	while (L < R) {
		M = L + R >> 1;
		if (cost(M+1) <= B)
			L = M+1;
		else R = M;
	}
	return L;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:43:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   M = L + R >> 1;
      |       ~~^~~

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