Submission #655260

#	Time	Username	Problem	Language	Result	Execution time	Memory
655260		600Mihnea	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1044 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;


typedef long long ll;

void solve(int n, int k, ll a, int skims) {

  vector<ll> v(n + 1), v2;
  set<int> s;
  for (int i = 1; i <= k; i++) {
    v[i] = skim(i);
    s.insert(i);
  }

  int low = 1, high = n, cnt_under = 0;
  v[n] = skim(n);
  while (low <= high) {
    int mid = (low + high) / 2;
    if (skim(mid) <= a) {
      cnt_under = mid;
      low = mid + 1;
    }
    else {
      high = mid - 1;
    }
  }
  for (int i = cnt_under - k; i <= cnt_under + 1; i++) {
    if (1 <= i && i <= n) {
      v[i] = skim(i);
      s.insert(i);
    }
  }
  vector<int> inds;
  for (auto& i : s) {
    inds.push_back(i);
    v2.push_back(v[i]);
  }

  for (int r = k - 1; r < (int)inds.size(); r++) {
    for (int c = 1; c <= k; c++) {
      ll sum = 0;
      for (int i = r - c + 1; i <= r; i++) {
        sum += v2[i];
      }
      for (int i = 0; i < k - c; i++) {
        sum += v2[i];
      }
      if (a <= sum && sum <= 2 * a) {
        vector<int> sol;
        for (int i = r - c + 1; i <= r; i++) {
          sol.push_back(inds[i]);
        }
        for (int i = 0; i < k - c; i++) {
          sol.push_back(inds[i]);
        }
        answer(sol);
        return;
      }

    }
  }

  impossible();
  return;
}

• 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