Submission #1134992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134992		eradax	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1084 ms	1196 KiB

books

#include <bits/stdc++.h>
#include "books.h"

// #define DBG
#ifdef DBG
#include "../../../dbg.h"
#else
#define dbg(...)
#endif

using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;

vl vals;
int N, K, S;
ll A;

const ll INF = 1e18;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, n) for (int i = s; i < (n); i++)

pair<vi, ll> rec(vi v, ll sum) {
  int i = 0;
  while (i < K && v[i] != -1) { i++; }

  dbg(i, v, sum);
  dbg(N, K, S, A);

  if (i == K) {
    return {v, sum};
  }

  int prev = i ? v[i - 1] : -1;

  dbg(prev, N - (K - i - 1));

  repp(j, prev + 1, N - (K - i - 1)) {
    vi vtmp = v; vtmp[i] = j;
    ll sumtmp = sum; sumtmp += vals[j];
    auto tmp = rec(vtmp, sumtmp);
    if (A <= tmp.second && tmp.second <= 2 * A) {
      return tmp;
    }
  } 

  return {vi(K, -1), INF};
}

void solve(int NN, int KK, ll AA, int SS) {
  N = NN;
  K = KK;
  A = AA;
  S = SS;

  vals.resize(N);

  rep(i, N) {
    vals[i] = skim(i + 1);
    S--;
  }

  auto [ans, sum] = rec(vi(K, -1), 0);
  rep(i, K) { ans[i]++; }

  dbg(ans, sum);

  if (A <= sum && sum <= 2 * A) {
    answer(ans);
  } else {
    impossible();
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20