# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1194391 | VMaksimoski008 | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
void solve(int n, int k, ll A, int s) {
vector<int> a(n+1);
vector<ll> pref(n+1);
for(int i=1; i<=n; i++) {
a[i] = skim(i);
pref[i] = a[i] + pref[i-1];
}
for(int i=1; i+k-1<=n; i++) {
ll sum = pref[i+k-1] - pref[i-1];
if(A <= sum && sum <= 2*A) {
vector<int> ans;
for(int j=i; j<=i+k-1; j++) ans.push_back(j);
answer(ans);
return ;
}
}
for(int i=2; i+k-2<=n; i++) {
ll sum = pref[i+k-2] - pref[i-1];
int l=1, r=i-1, p=0;
while(l <= r) {
int mid = (l + r) / 2;
if(A <= sum + a[mid]) p = mid, r = mid - 1;
else l = mid + 1;
}
if(p && sum + a[mid] <= 2 * A) {
vector<int> ans = { mid };
for(int j=i; j<=i+k-2; j++) ans.push_back(j);
answer(ans);
return ''
}
}
impossible();
}