Submission #235841

#	Time	Username	Problem	Language	Result	Execution time	Memory
235841		Dilshod_Imomov	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1090 ms	696 KiB

ricehub

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

int besthub(int n, int mx, int a[], long long b)
{
	int ans = 1;
	for ( int i = 0; i < n; i++ ) {
		int x = a[i];
		vector < int > vc;
		vc.push_back( 0 );
		for ( int j = i - 1; j >= 0; j-- ) {
			vc.push_back( vc.back() + (x - a[j]) );
		}
		// cout << x << '\n';
		// for ( auto j: vc ) {
		// 	cout << j << ' ';
		// }
		// cout << "\n";
		long long pr = 0;
		for ( int j = i + 1; j < n; j++ ) {
			pr += a[j] - x;
			int left = b - pr;
			// cout << a[j] << ' ' << left << '\n';
			if ( left < 0 ) {
				continue;
			}
			ans = max( ans, j - i + 1 );
			auto it = upper_bound( vc.begin(), vc.end(), left );
			// it--;
			if ( it != vc.begin() ) {
				it--;
			}
			int ind = it - vc.begin();
			// cout << a[j] << ' ' << pr << ' ' << ind << '\n';
			ans = max( ans, j - i + ind + 1 );
		}
	}
	return ans;
}

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