Submission #399269

#	Time	Username	Problem	Language	Result	Execution time	Memory
399269		LucaDantas	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1868 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

constexpr int logn = 20, maxn = 2e5+10;

long long dp[maxn];

long long get(int x) {
	if(dp[x] != -1) return dp[x];
	dp[x] = skim(x);
	return dp[x];
}

void solve(int N, int k, long long A, int S) {
	memset(dp, -1, sizeof dp);
	int pos = N+1;
	int l = 1, r = N;
	while(l <= r) {
		int m = (l+r) >> 1;
		if(get(m) >= A) pos = m, r = m-1;
		else l = m+1;
	}
	
	if(pos < k) impossible();

	long long menores = 0;
	for(int i = 1; i < k; i++) {
		menores += get(i);
		if(menores > 2*A) impossible();
	}
	
	if(pos <= N && menores + get(pos) <= 2*A) {
		vector<int> ans;
		for(int i = 1; i < min(k, pos); i++)
			ans.push_back(i);
		ans.push_back(pos);
		answer(ans);
		return;
	}

	if(pos == k) impossible();

	N = pos - 1;

	for(int i = 0; i <= k; i++) {
		long long sum = 0;
		vector<int> ans;
		
		for(int j = 1; j <= i; j++)
			sum += get(j), ans.push_back(j);
		
		for(int j = N - k + i + 1; j <= N; j++)
			sum += get(j), ans.push_back(j);

		if(sum >= A && sum <= 2*A)
			answer(ans);
	}

	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