제출 #1150004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150004		weakweakweak	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	24 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
    long long sum = 0;
    vector<pair<int,long long>> z;
    for (int i = 1; i < K; i++) {
        z.push_back(make_pair(i,skim(i)));
        sum += z.back().second;
    }
    if (sum > 2*A) impossible();
    int ll = K-1, rr = N-1;
    while (ll < rr) {
        int mid = (ll+rr+1) / 2;
        if (skim(mid)+sum <= A) ll = mid;
        else rr=mid-1;
    }
    ll++;    

    long long tmp = skim(ll);
    z.push_back(make_pair(ll,tmp));


    for (int i = max(K,ll-K); i < ll; 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: 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