Submission #1200595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200595		crispxx	Rice Hub (IOI11_ricehub)	C++20	68 / 100	67 ms	584 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

// #include "grader.cpp"

int besthub(int n, int l, int x[], long long B) {
	int ans = 0;
	for(int i = n / 2; i < n; i++) {
		int l = i - 1, r = i + 1, cost = 0, res = 1;
		while(l >= 0 && r < n) {
			int a = x[i] - x[l], b = x[r] - x[i];
			if(a < b) {
				if(cost + a > B) break;
				cost += a;
				l--;
			} else {
				if(cost + b > B) break;
				cost += b;
				r++;
			}
			res++;
		}
		while(l >= 0) {
			int a = x[i] - x[l];
			if(cost + a > B) break;
			cost += a;
			l--;
			res++;
		}
		while(r < n) {
			int a = x[r] - x[i];
			if(cost + a > B) break;
			cost += a;
			r++;
			res++;
		}
		ans = max(ans, res);
		if(ans == n) return n;
	}
	
	for(int i = n / 2 - 1; i >= 0; i--) {
		int l = i - 1, r = i + 1, cost = 0, res = 1;
		while(l >= 0 && r < n) {
			int a = x[i] - x[l], b = x[r] - x[i];
			if(a < b) {
				if(cost + a > B) break;
				cost += a;
				l--;
			} else {
				if(cost + b > B) break;
				cost += b;
				r++;
			}
			res++;
		}
		while(l >= 0) {
			int a = x[i] - x[l];
			if(cost + a > B) break;
			cost += a;
			l--;
			res++;
		}
		while(r < n) {
			int a = x[r] - x[i];
			if(cost + a > B) break;
			cost += a;
			r++;
			res++;
		}
		ans = max(ans, res);
		if(ans == n) return n;
	}
	
	return ans;
}

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