Submission #398490

#	Time	Username	Problem	Language	Result	Execution time	Memory
398490		iulia13	Rice Hub (IOI11_ricehub)	C++14	58 / 100	21 ms	2508 KiB

ricehub

#include <iostream>
#include <vector>
#include "ricehub.h"
using namespace std;
const int nmax = 1e5 + 5;
#define ll long long
ll pref[nmax];
ll suf[nmax];
int besthub(int n, int l, int v[], ll b)
{
    int i;
    for (i = 0; i < n; i++)
        pref[i] = pref[i - 1] + 1ll * v[i];
    int st = 1, dr = n, sol = 0;
    while (st <= dr)
    {
        int mid = (st + dr) / 2, ok = 1;
        for (i = 0; ok && i < n - mid + 1; i++)
        {
            ///de la i la i + mid - 1
            int poz = mid / 2 + i - 1;
            ll money = 1ll * (poz - i) * v[poz] - 1ll * (i + mid - 1 - poz) * v[poz];
            money -= (pref[poz - 1] - pref[i - 1]);
            money += pref[i + mid - 1] - pref[poz];
            if (money <= b)
                ok = 0;
        }
        if (!ok)
        {
            sol = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return sol;
}
vector <int> dani;/*
int main()
{
    int r, l;
    cin >> r >> l;
    dani.resize(r);
    for (int i = 0; i < r; i++)
        cin >> dani[i];
    ll b;
    cin >> b;
    cout << besthub(r, l, dani, b);
    return 0;
}*/

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