Submission #1149992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149992		weakweakweak	A Difficult(y) Choice (BOI21_books)	C++20	45 / 100	42 ms	408 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this 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, long long A, int S) {
    // TODO implement this function
    int ll = 1, rr = N;
    while (ll < rr) {
        int mid = (ll+rr) / 2;
        if (skim(mid)*K >= A) rr = mid;
        else ll = mid+1;
    }
    
    vector<pair<int,long long>> z;
    for (int i = max(1, ll-K); i <= min(N, ll+K); i++) {
        z.push_back(make_pair(i,skim(i)));
    }
    
    int n2 = z.size();
    for (int i = (1<<n2)-1; i >= 0; i--) {
        if (__builtin_popcount(i) != K) continue;
        long long sum = 0;
        vector<int> v;
        for (int j = 0; j < n2; j++) {
            if ((i>>j)&1) {
                sum += z[j].second;
                if (sum > A * 2) break;
                v.push_back(z[j].first);
            }
        }
        if (sum >= A and sum <= A * 2) {
            answer(v);
        }

    }
    impossible();
}

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