Submission #611046

#	Time	Username	Problem	Language	Result	Execution time	Memory
611046		DanerZein	A Difficult(y) Choice (BOI21_books)	C++14	60 / 100	2 ms	1052 KiB

books

#include <bits/stdc++.h>
 
#include "books.h"
 
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
typedef long long ll;
const int MAX_N=1e5+10;
vector<ll> book;
ll libro(int id){
  if(book[id]!=-1) return book[id];
  return book[id]=skim(id);
}
void solve(int N, int K, long long A, int S) {
  book.resize(N+1);
  for(int i=0;i<=N;i++) book[i]=-1;
  for(int i=1;i<K;i++){
    book[i]=libro(i);
  }
  ll sk=0;
  vector<int> ans;
  for(int i=1;i<K;i++){
    sk+=libro(i);
    ans.push_back(i);
  }
  if(sk>=A){
    if(sk+skim(K)>2*A) impossible();
    else{
      ans.push_back(K);
      answer(ans);
    }
  }
  bool ok=0;
  int l=0,r=N;
  while(r-l>1){
    int mid=(l+r)/2;
    if(libro(mid)>=A) r=mid;
    else l=mid+1;
  }
  int id=r;
  if(libro(l)>=A) id=l;
  if(sk+libro(id)>=A && sk+libro(id)<=2LL*A){
    ans.push_back(id);
    ok=1;
  }
  else{
    if(libro(id)>=A)
      id--;
    sk+=libro(id);
    ans.push_back(id);
    id--;
    for(int i=0;i<K-1;i++){
      int mi=ans[0];
      ans.erase(ans.begin());
      ans.push_back(id);
      sk-=libro(mi); sk+=libro(id);
      if(sk>=A){
	ok=1;
	break;
      }
      id--;
    }
  }
  if(!ok) impossible();
  else answer(ans);
}

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