제출 #398494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398494		iulia13	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	19 ms	1484 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 = (2 * i + mid - 1) / 2;
            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;
}/*
int dani[nmax];
int main()
{
    int r, l; ll b;
    cin >> r >> l >> b;
    for (int i = 0; i < r; i++)
        cin >> dani[i];

    //cin >> b;
    cout << besthub(r, l, dani, b);
    return 0;
}*/

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