Submission #336115

#	Time	Username	Problem	Language	Result	Execution time	Memory
336115		knightron0	Rice Hub (IOI11_ricehub)	C++14	100 / 100	38 ms	2284 KiB

ricehub

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

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;


long long int a[MAXN], pref[MAXN];
long long int n;


bool check(long long int x, long long int b){
	for(long long int i= 1;i<=n-x+1;i++){
		vector<long long int> md;
		if(x & 1){
			md.pb((i + i +x-1)/2);
		} else {
			md.pb((i + i +x-1)/2);
			md.pb(((i + i +x-1)/2)+1);
		}
		for(long long int m: md){
			long long int sum1 = (long long int)pref[m]-(long long int)pref[i-1];
			sum1 *= -1;
			sum1 += (long long int)(m-(i-1))*(long long int)a[m];
			long long int sum2 = (long long int)pref[i+x-1]-(long long int)pref[m];
			sum2 -= (long long int)(i+x-1-m)*(long long int)a[m];
			long long int sum = sum1+sum2;
			if(sum <= b){
				return true;
			}
		}
	}
	return false;
}


int besthub(int r, int l, int x[], long long int b) {
	n = r;
	pref[0] = 0;
	for(int i= 1;i<=n;i++){
		a[i] = (long long int)x[i-1];
		pref[i] =  (long long int)pref[i-1] + (long long int)a[i];
	}
	int lo = 1;
    int hi = n;
    while(lo <= hi){
    	int mid = lo+(hi-lo)/2;
    	if(check((long long int) mid, b)){
    		lo = mid+1;
    	} else {
    		hi = mid-1;
    	}
    }
    if(!check(lo, b)){
    	return hi;
    }
    return lo;

}

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