fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. bool isValid(ll books, ll studentsGiven, vector<ll> &pages, ll pageLimit) {
  5.     ll studentsNeeded = 1, pagesReadByCurrStudent = pages[0];
  6.     if (pages[0] > pageLimit) {
  7.         return false;
  8.     }
  9.     for (int i = 1; i < books; i++) {
  10.         if (pages[i] > pageLimit) {
  11.             return false;
  12.         }
  13.         if (pagesReadByCurrStudent + pages[i] > pageLimit) {
  14.             studentsNeeded++;
  15.             pagesReadByCurrStudent = 0;
  16.             i--;
  17.         }
  18.         else {
  19.             pagesReadByCurrStudent += pages[i];
  20.         }
  21.     }
  22.     return studentsGiven >= studentsNeeded;
  23. }
  24. ll findMaxPages(ll books, ll students, vector<ll> &pages, ll s, ll e, ll sum) {
  25.     ll pagesRead = e;
  26.     while (s <= e) {
  27.         ll m = s + (e-s)/2;
  28.         if (isValid(books, students, pages, m)) {
  29.             pagesRead = m;
  30.             e = m-1;
  31.         }
  32.         else {
  33.             s = m+1;
  34.         }
  35.     }
  36.     return pagesRead;
  37. }
  38. int main() {
  39.     ll books, students, sum = 0;
  40.     cin >> books >> students;
  41.     vector<ll> pages(books);
  42.     for (ll i = 0; i < books; i++) {
  43.         cin >> pages[i];
  44.         sum += pages[i];
  45.     }
  46.     cout << findMaxPages(books, students, pages, 0, sum, sum);
  47.     return 0;
  48. }
Runtime error #stdin #stdout #stderr 0s 4568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/P53XxQ
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!