제출 #1283461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283461		weebyeah	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	2 ms	408 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

#define Ilveyuki ios::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
//
// --- Sample implementation for the task books ---
//
// To compile trs program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int K, ll A, int S)
{
    map<int, ll> m;

    int l = 1, r = N + 1;
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        ll v;
        auto it = m.find(mid);

        if (it == m.end())
        {
            v = skim(mid);
            m[mid] = v;
        }
        else
            v = it -> second;

        if (v > A)
            r = mid;
        else
            l = mid + 1;
    }

    int t = l;

    vector<ll> lv;
    for (int i = 1; i <= K; i++)
    {
        ll v;
        auto it = m.find(i);

        if (it == m.end())
        {
            v = skim(i);
            m[i] = v;
        }
        else
            v = it -> second;

        lv.push_back(v);
    }

    vector<ll> lp(K + 1);
    for (int i = 1; i <= K; i++)
    {
        lp[i] = lp[i - 1] + lv[i - 1];
    }

    if (t <= N)
    {
        ll xt;
        auto it = m.find(t);

        if (it == m.end())
        {
            xt = skim(t);
            m[t] = xt;
        }
        else
            xt = it -> second;

        ll tot = lp[K - 1] + xt;
        if (A <= tot && tot <= 2 * A)
        {
            vector<int> res;
            for (int i = 1; i <= K - 1; i++)
            {
                res.push_back(i);
            }

            res.push_back(t);
            answer(res);

            return;
        }
    }

    if (t - 1 < K)
    {
        impossible();
        return;
    }

    vector<ll> rv;
    int ss = t - K;
    for (int i = ss; i <= t - 1; i++)
    {
        ll v;
        auto it = m.find(i);

        if (it == m.end())
        {
            v = skim(i);
            m[i] = v;
        }
        else
            v = it -> second;

        rv.push_back(v);
    }

    vector<ll> rs(K + 1);
    for (int i = 1; i <= K; i++)
    {
        rs[i] = rs[i - 1] + rv[K - i];
    }

    for (int i = 0; i <= K; i++)
    {
        ll tot = lp[K - i] + rs[i];
        if (A <= tot && tot <= 2 * A)
        {
            vector<int> res;
            for (int j = 1; j <= K - i; j++)
            {
                res.push_back(j);
            }

            for (int j = t - i; j <= t - 1; j++)
            {
                res.push_back(j);
            }

            answer(res);
            return;
        }
    }

    impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20