Submission #377661

#	Time	Username	Problem	Language	Result	Execution time	Memory
377661		jlallas384	Rice Hub (IOI11_ricehub)	C++14	100 / 100	21 ms	2540 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;
using ll = long long;

ll pref[100100];
ll sum(int l,int r){
	return pref[r+1] - pref[l];
}

int besthub(int n, int ln, int x[], ll b){
	for(int i = 0; i < n; i++){
        pref[i+1] = pref[i] + x[i];
    }
    int ans = 0,r = 0;
    for(int l = 0; l < n; l++){
        while(r < n){
            ll res = 0;
            if(r - l == 1) res = x[r] - x[l];
            else if(r - l != 0){
                int md = l + (r-l)/2;
                int cnt = (r-l+1)/2;
                ll up = sum(md+1,r) - (ll) cnt * x[md];
                ll down = (ll) x[md] * (cnt - (r - l) % 2) - sum(l,md-1);
                res = up + down;
            }
            if(res > b) break;
            else{
                ans = max(ans,r - l + 1);
                r++;
            }
        }
    }
    return ans;
}

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