Submission #903882

#	Time	Username	Problem	Language	Result	Execution time	Memory
903882		oblantis	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	4456 KiB

ricehub

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "ricehub.h"
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
int besthub(int n, int L, int x[], long long b){
	int xl = 1, xr = n + 1;
	ll p[n];
	for(int i = 0; i < n; i++){
		p[i] = x[i];
		if(i)p[i] += p[i - 1];
	}
	while(xl + 1 < xr){
		bool ok = 0;
		int mid = xl + (xr - xl) / 2;
		for(int i = mid - 1; i < n; i++){
			int j = i - mid / 2;
			ll s = p[i] - p[j] * 2;
			if(i != mid - 1)s += p[i - mid];
			if(mid % 2)s += x[j];
			if(s <= b)ok = 1;
		}
		if(ok)xl = mid;
		else xr = mid;
	}
	return xl;
}

//void solve() {
	//int n, l, b;
	//cin >> n >> l >> b;
	//int x[n];
	//for(int i = 0; i < n; i++)cin >> x[i];
	//cout << besthub(n, l, x, b);
//}
//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}

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