Submission #198961

#	Time	Username	Problem	Language	Result	Execution time	Memory
198961		godwind	Rice Hub (IOI11_ricehub)	C++14	0 / 100	8 ms	632 KiB

ricehub

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
// #include "grader.h"

using namespace std;


#define ll long long
#define ld double
#define null NULL
#define prev prev228
#define index index228
#define left left228
#define right right228
#define hash hash228
#define y1 y1228
#define firn(i, n) for (int i = 0; i < (int)n; ++i)
#define forn(i, n) for (int i = 1; i <= (int)n; ++i)
#define endl '\n'


template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}

template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 100 * 1000 + 228;

long long sum[N];
int x[N];

long long f(int l, int r, int i) {
	long long res = 0LL; 
	res += (sum[r] - sum[i]) - (long long)x[i - 1] * (long long)(r - i);
	res += (long long)x[i - 1] * (long long)(i - l) - (sum[i - 1] - sum[l - 1]);
	return res;
}

int besthub(int n, int L, int X[], long long B){  
	for (int i = 0; i < n; ++i) {
		x[i] = X[i];
	}
	for (int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + x[i - 1];
	}
	int k = 1;
	for (int i = 1; i <= n; ++i) {
		int l = i - k / 2, r = i + k / 2;
		if (l < 1 || r > n) continue;
		while (l > 1 && r < n && f(l - 1, r + 1, i) <= B) {
			--l;
			++r;
		}
		uax(k, r - l + 1);
		if (r < n && f(l, r + 1, i) <= B) uax(k, r - l + 2);
		if (l > 1 && f(l - 1, r, i) <= B) uax(k, r - l + 2);
	}
	return k;
}

// int X[N];

// signed main() {
// 	X[0] = 1, X[1] = 2, X[2] = 10, X[3] = 12, X[4] = 14;
// 	cout << besthub(5, 20, X, 6LL) << '\n';
// }

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