Submission #466369

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

void solve(int N, int K, long long A, int S) {
	int l = 1, r = N, idx = N + 1;
	ll B = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		ll x = skim(mid);
		if (x > A) {
			idx = mid, r = mid - 1, B = x;
		}
		else l = mid + 1;
	}
	if (idx <= K - 1) {
		impossible();
		return ;
	}
	vector<pair<int, ll> > num;
	ll sum = 0;
	rep(i, 1, K - 1) {
		ll x = skim(i);
		sum += x;
		num.pb(mp(i, x));
	}
	num.pb(mp(K, skim(K)));
	if (idx != N + 1 && sum + B >= A && sum + B <= 2 * A) {
		vector<int> ans;
		rep(i, 1, K - 1) ans.pb(i);
		ans.pb(idx);
		answer(ans);
		return ;
	}
	rep(i, max(K + 1, idx - K), idx - 1)
		num.pb(mp(i, skim(i)));
	
	rep(i, 0, sz(num) - K) {
		ll sum = 0;
		rep(j, i, i + K - 1) {
			sum += num[j].se;
		}
		if (sum >= A && sum <= 2 * A) {
			vector<int> ans;
			rep(j, i, i + K - 1)
				ans.pb(num[j].fi);
			answer(ans);
			return ;
		}
	}
	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