Submission #1182799

#TimeUsernameProblemLanguageResultExecution timeMemory
1182799razivoA Difficult(y) Choice (BOI21_books)C++20
0 / 100
0 ms1164 KiB
#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-1; ++i) { int t = sskim(i).second; l+=t; rel.push_back({l,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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...