Submission #1148764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148764		sano	Rice Hub (IOI11_ricehub)	C++20	100 / 100	10 ms	2692 KiB

ricehub

#include "ricehub.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 10000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<ll> ps;

bool check(ll s, ll d, vec<ll>&x, ll b) {
	ll h1 = (-1) * (ps[s] - ps[s - d]) + d * x[s];
	ll h2 = (ps[s + d + 1] - ps[s + 1]) - d * x[s];
	return (h1 + h2) <= b;
}

int besthub(int r1, int l1, int x1[], ll b) {
	ll r = r1;
	ll l = l1;
	vec<ll> x;
	For(i, r) x.push_back(x1[i]);
	ps.resize(r + 1, 0);
	For(i, r) {
		ps[i + 1] = ps[i] + x[i];
	}
	ll maxi = -1;
	For(i, r) {
		ll l = 0;
		ll ri = min(i, r - i - 1);
		while (l < ri) {
			ll mid = (l + ri + 1) / 2;
			if (check(i, mid, x, b)) {
				l = mid;
			}
			else {
				ri = mid - 1;
			}
		}
		maxi = max(maxi, 2 * l + 1);
		if ((i + l + 1) < r) {
			ll d = l;
			ll h1 = (-1) * (ps[i] - ps[i - d]) + d * x[i];
			ll h2 = (ps[i + d + 2] - ps[i + 1]) - (d + 1) * x[i];
			if ((h1 + h2) <= b) {
				maxi = max(maxi, 2 * l + 2);
			}
		}
	}
	return maxi;
}
/*
int main() {
	int r, l;
	ll b;
	cin >> r >> l >> b;
	int x[1000];
	For(i, r) cin >> x[i];
	cout << besthub(r, l, x, b) << '\n';
	return 0;
}*/

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