Submission #233361

#	Time	Username	Problem	Language	Result	Execution time	Memory
233361		Coroian_David	Rice Hub (IOI11_ricehub)	C++11	100 / 100	24 ms	3448 KiB

ricehub

#include <bits/stdc++.h>

#include "ricehub.h"

#define MAX_R 100000
#define MAX_N 100000

using namespace std;

typedef long long lint;

int n;

lint v[MAX_N + 1];
lint sum[MAX_N + 1];
lint bani;

bool pos(int len)
{
   // cout << " INTRA LEN " << len << "\n";

  // cout << sum[n] << "\n";

    for(int i = len; i <= n; i ++)
    {
        int st = i - len + 1;

        int med = ((len + 1) >> 1);
        int p = st - 1 + med;

       // cout << " SPRE ST AVEM " << med * v[p] << " - " << (sum[p] - sum[st - 1]) << "\n";
       // cout << " SPRE DR AVEM " << (sum[i] - sum[p]) << " - " <<  (i - med) * v[p] << "\n";

        lint cost = med * v[p] - (sum[p] - sum[st - 1]) +
                    (sum[i] - sum[p]) - (i - p) * v[p];

       // if(len <= 4)
        //cout << " SUNTEM " << st << " " << p << " " << i << " len " << len << " COSt " << cost << "\n";

        if(cost <= bani)
            return 1;
    }

    return 0;
}

int cautBin()
{
    int i = 0;
    int pas = 1 << 16;
    while(pas != 0)
    {
        if(i + pas <= n && pos(i + pas) == 1)
            i += pas;

        pas >>= 1;
    }

    return i;
}

int besthub(int R, int L, int X[], long long B)
{
    bani = B;
    n = R;

    sum[1] = X[0];
    v[1] = X[0];
    for(int i = 2; i <= n; i ++)
    {
        v[i] = X[i - 1];
        sum[i] = sum[i - 1] + v[i];
    }

    int rez = cautBin();

    return rez;
}

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