oj.uz

Submission #235850

# Submission time Handle Problem Language Result Execution time Memory
235850 2020-05-30T07:38:58 Z Dilshod_Imomov Rice Hub (IOI11_ricehub) C++17
68 / 100
 118 ms 2220 KB 
#include "ricehub.h"	
#include <bits/stdc++.h>
using namespace std;
// # define int long long

long long ps[100100];

int besthub(int n, int mx, int a[], long long b)
{
	for ( int i = 0; i < n; i++ ) {
		ps[i] = a[i];
		if ( i ) {
			ps[i] += ps[i - 1];
		}
	}
	int ans = 1;
	for ( int i = 0; i < n; i++ ) {
		int x = a[i];
		// cout << x << '\n';
		// for ( auto j: vc ) {
		// 	cout << j << ' ';
		// }
		// cout << "\n";
		int l = i + 1, r = n - 1, mid;
		while ( l <= r ) {
			mid = (l + r) / 2;
			int sum = ps[mid] - ps[i];
			sum -= (mid - i) * x;
			int left = b - sum;
			if ( left < 0 ) {
				r = mid - 1;
			}
			else {
				// cout << mid << '\n';
				ans = max( ans, mid - i + 1 );
				int ll = 0, rr = i - 1, mid1, ind = i;
				while ( ll <= rr ) {
					mid1 = (ll + rr) / 2;
					int sum1 = ps[i - 1];
					if ( mid1 ) {
						sum1 -= ps[mid1 - 1];
					}
					sum1 = (i - mid1) * x - sum1;
					if ( sum1 > left ) {
						ll = mid1 + 1;
					}
					else {
						rr = mid1 - 1;
						ind = mid1;
					}
				}
				/*
				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, (mid - i) + (i - ind) + 1 );
				l = mid + 1;
			}
		}
		/*
		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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 380 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 7 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 8 ms 512 KB Output is correct
25 Correct 7 ms 512 KB Output is correct
26 Correct 8 ms 384 KB Output is correct
27 Correct 9 ms 384 KB Output is correct
28 Correct 8 ms 384 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 11 ms 768 KB Output is correct
3 Correct 93 ms 2176 KB Output is correct
4 Incorrect 118 ms 2220 KB Output isn't correct
5 Halted 0 ms 0 KB -