fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. int v[16003],n,k,maxi = 0;
  5. int noftt(int c)
  6. {
  7.     int i = 0, cur = 0, noft = 0;
  8.     while( i < n)
  9.     {
  10.         if (cur+v[i] <=  c)
  11.             cur +=v[i];
  12.         else
  13.         {
  14.             cur = v[i];
  15.             noft++;
  16.         }
  17.         i++;
  18.     }
  19.     if( cur!=0)
  20.         noft++;
  21.     return noft;
  22. }
  23. int BS(int st , int dr)
  24. {
  25.     while( st<=dr)
  26.     {
  27.         int mij = (st+dr)/2;
  28.         int n_o_t = noftt(mij);
  29.         if (n_o_t == k)
  30.         {
  31.             if( noftt(mij-1) >k)
  32.                 return mij;
  33.             else
  34.                 dr = mij-1;
  35.         }
  36.         if( n_o_t < k )
  37.             dr = mij-1;
  38.         if( n_o_t > k)
  39.             st = mij+1;
  40.     }
  41. }
  42.  int main()
  43. {
  44.     cin >> n >> k;
  45.     for(int i = 0 ; i < n ; i++)
  46.     {
  47.         cin >>v[i];
  48.         if (v[i]> maxi)
  49.             maxi = v[i];
  50.     }
  51.     int result = BS(maxi,n*16000);
  52.     cout<< result;
  53.     return 0;
  54. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
3 3
1
2
3
stdout
copy 
134517452
https://ideone.com/E9OBsq
language:
C++14 (gcc 8.3)
created:
8 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!