Submission #1182840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182840		razivo	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	26 ms	1164 KiB

books

#include "books.h"
#include <bitset>
using namespace std;
vector<long long> res;
pair<long long,long long> sskim(int l) {
    if(res[l] ==-1) {
        long long t = skim(l+1);
        res[l]=t;
        return {t,t};
    }else {
        return {res[l],res[l]};
    }
}
void solve(int N, int K, long long A, int S) {
    long long l = 0;
    res = vector<long long>(N,-1);
    vector<pair<int,long long>> rel;
    for (int i = 0; i < K; ++i) {
        long long t = sskim(i).second;
        if(i!=K-1)l+=t;
        rel.push_back({i,t});
    }
    int min = 0;
    int max = N;
    while(max-min>1) {
        int mid = (min+max)/2;
        if(sskim(mid).second>2*A-l) {
            max = mid;
        }else {
            min = mid;
        }
    }
    for (int i = min; i >= std::max(min-K,K); --i) {
        auto [a,b] = sskim(i);
        rel.push_back({i,sskim(i).second});
    }
    int v = rel.size();
    for (int i = 0; i < 1<<v; ++i) {
        bitset<20> b = i;
        long long r = 0;
        if(b.count()!=K) continue;
        for (int j = 0; j < v; ++j) {
            if(b[j]) r+=rel[j].second;
        }
        if(r<=2*A && A<=r) {
            vector<int> re;
            for (int j = 0; j < v; ++j) {
                if(b[j]) re.push_back(rel[j].first+1);

            }
            answer(re);
            exit(0);
        }
    }
    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