제출 #235864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235864		Dilshod_Imomov	쌀 창고 (IOI11_ricehub)	C++17	68 / 100	163 ms	1656 KiB

ricehub

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

long long ps[100100];

int besthub(int n, int mx, int a[], long long b)
{
	for ( LL i = 0; i < n; i++ ) {
		ps[i] = a[i];
		if ( i ) {
			ps[i] += ps[i - 1];
		}
	}
	LL ans = 1;
	for ( LL i = 0; i < n; i++ ) {
		LL x = a[i];
		LL l = i, r = n - 1, mid;
		while ( l <= r ) {
			mid = (l + r) / 2;
			long long sum = ps[mid] - ps[i];
			sum -= (mid - i) * x;
			long long left = b - sum;
			if ( left < 0 ) {
				r = mid - 1;
			}
			else {
				ans = max( ans, mid - i + 1 );
				LL ll = 0, rr = i, mid1, ind = i;
				while ( ll <= rr ) {
					mid1 = (ll + rr) / 2;
					long long 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;
						ans = max( ans, (mid - i) + (i - ind) + 1 );
					}
				}
				ll = 0;rr = ind - 1;
				ind = i;
				while ( ll <= rr ) {
					mid1 = (ll + rr) / 2;
					long long 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;
						ans = max( ans, (mid - i) + (i - ind) + 1 );
					}
				}
				ans = max( ans, (mid - i) + (i - ind) + 1 );
				l = mid + 1;
			}
		}
	}
	return ans;
}

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