Submission #261630

#	Time	Username	Problem	Language	Result	Execution time	Memory
261630		c4ts0up	Rice Hub (IOI11_ricehub)	C++17	17 / 100	23 ms	1912 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
vector <ll> arr;

int besthub(int R, int L, int X[], ll B) {
	//cerr << "Entrando a besthub..." << endl;
	
	n = (ll)R;
	
	// creamos el arreglo
	for (ll i=0; i<n; i++) arr.push_back((ll)X[i]);
	
	ll lb = 0, ub = 0, suma = 0LL, prev, maxi = 1LL;
	
	//cerr << "Entrando al loop..." << endl;
	for (ll i=0; i<n; i++) {
		//cerr << "I = " << i << endl;
		// 1. Actualizamos la suma
		if (!i) {} // no toca si i == 0
		else {
			//cerr << "La suma paso de " << suma << " a ";
			
			suma -= ((ub-(i-1))*(abs(prev-arr[i])));
			suma += ((i-lb)*(abs(prev-arr[i])));
			
			//cerr << suma << endl;
		}
		
		// 2. Recogemos lb
		while (suma > B) {
			suma -= abs(arr[lb]-arr[i]);
			lb++;
		}
		
		// 3. Expandimos ub
		while (ub+1 < n) {
			if (suma + abs(arr[ub+1]-arr[i]) <= B) suma += abs(arr[ub+1]-arr[i]), ub++;
			else break;
		}
		
		//cerr << "Nuevos valores, lb = " << lb << ", ub = " << ub << endl;
		
		// 4. Contar
		maxi = max(maxi, ub-lb+1);
		
		prev = arr[i];
	}
	
	return maxi;
}

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