Submission #795860

#	Time	Username	Problem	Language	Result	Execution time	Memory
795860		KLPP	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	145 ms	320 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
//
// --- 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.
//
map<int,lld> m;
int n;
lld query(int pos){
	if(m.find(pos)==m.end()){
		lld x=skim(pos+1);
		m[pos]=x;
		return x;
	}
	return m[pos];
}
void solve(int N, int K, long long A, int S) {
	n=N;
    int lo=-1;
    int hi=N;
    while(hi-lo>1){
		int mid=(hi+lo)/2;
		if(query(mid)<=A){
			lo=mid;
		}else hi=mid;
	}
	if(lo==-1)impossible();
	vector<pair<lld,int> > books;
	int k=K;
	rep(i,0,k){
		books.push_back({query(i),i});
	}
	for(int i=lo;i>lo-k && i>=0;i--){
		books.push_back({query(i),i});
	}
	assert(m.size()<40);
	if(lo+1<N){
		books.push_back({query(lo+1),lo+1});
	}
	sort(books.begin(),books.end());
	books.resize(unique(books.begin(),books.end())-books.begin());
	vector<int> St;
	rep(msk,0,(1<<books.size())){
		lld sum=0;
		St.clear();
		rep(i,0,(int)books.size()){
			if((msk&(1<<i))>0){
				St.push_back(books[i].second+1);
				sum+=books[i].first;
			}
		}
		if(sum>=A && sum<=2*A && (int)St.size()==k){
			answer(St);
		}
	}
	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