제출 #611009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611009		DanerZein	A Difficult(y) Choice (BOI21_books)	C++14	20 / 100	218 ms	712 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;
void solve(int N, int K, long long A, int S) {
  book.push_back(0);
  for(int i=1;i<=N;i++){
    book.push_back(skim(i));
  }
  ll sk=0;
  vector<int> ans;
  for(int i=1;i<K;i++){
    sk+=book[i];
    ans.push_back(i);
  }
  if(sk+book[K]>=A){
    if(sk+book[K]>2*A) impossible();
    else{
      ans.push_back(K);
      answer(ans);
    }
  }
  bool ok=0;
  auto it=lower_bound(book.begin(),book.end(),A);
  int id=it-book.begin();
  if(sk+book[id]>=A && sk+book[id]<=2LL*A){
    ans.push_back(id);
    ok=1;
  }
  else{
    id--;
    sk+=book[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-=book[mi]; sk+=book[id];
      if(sk>=A){
	ok=1;
	break;
      }
      id--;
    }
    /*for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    cout<<endl;
    cout<<sk<<endl;*/
  }
  if(!ok) impossible();
  else answer(ans);
}

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