Submission #893125

#	Time	Username	Problem	Language	Result	Execution time	Memory
893125		AgentPengin	Rice Hub (IOI11_ricehub)	C++14	100 / 100	14 ms	3676 KiB

ricehub

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

int n,x[MAXN],max_len;
ll b,px[MAXN];

bool check(int mid) {
	for (int L = 1;L + mid - 1 <= n;L++) {
		int R = L + mid - 1;
		int tv = (L + R) >> 1;
		ll cost = (ll)x[tv] * ((ll)tv - L + 1) - (px[tv] - px[L - 1]);
		cost += (px[R] - px[tv]) - x[tv] * (R - (ll)tv);
		if (cost <= b) return true;
	}
	return false;
}

int besthub(int R,int L,int X[],ll B) {
	n = R,max_len = L,b = B;
    for (int i = 1;i <= n;i++) x[i] = X[i - 1];
    sort(x + 1,x + n + 1);
    for (int i = 1;i <= n;i++) px[i] = px[i - 1] + (ll)x[i];
    int l = 2,r = n,ans = 1;
    while(l <= r) {
    	int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return ans;
}

// signed main() {
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // if (ifstream(NAME".inp")) {
        // freopen(NAME".inp","r",stdin);
        // freopen(NAME".out","w",stdout);
    // }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    // return 0;
// }
// // agent pengin wants to take apio (with anya-san)

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