Submission #584648

#	Time	Username	Problem	Language	Result	Execution time	Memory
584648		teki	Rice Hub (IOI11_ricehub)	C++11	0 / 100	3 ms	468 KiB

ricehub

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

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
const ll MN = 1000000007;

using namespace std;

int besthub(int n, int l, int poz[], ll b) {
    ll prefSuma[n];
    MS(prefSuma,0);

    for (ll i = 0; i<n; i++) {
        prefSuma[i] = poz[i];
        if (i != 0) prefSuma[i] += prefSuma[i-1];
    }

    ll from = 0;
    ll res = 0;

    for (ll to = 0; to<n; to++) {
        ll mid = (from+to)/2;

        ll levoS = mid-from;
        ll desnoS = to-mid;

        ll necBud = levoS*poz[mid];
        necBud -= prefSuma[mid-1];
        if (from != 0) necBud += prefSuma[from-1];

        if (to > mid) {
            necBud += prefSuma[to];
            if (to != 0) necBud -= prefSuma[to-1];
            necBud -= desnoS*poz[mid];
        }

        if (necBud > b) from++;
        else res = max(res,to-from+1);
    }

    return res;

}

//int main()
//{
//    #if LOCAL_DEBUG
//        fstream cin("in.txt");
//    #endif
//
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
//
//    cout<<ricehub(5,20,{1,2,10,12,14},6)<<endl;
//
//    return 0;
//}

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