Cod sursa(job #2491800)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 13 noiembrie 2019 10:02:13
Problema Transport Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>

using namespace std;

ifstream in ("transport.in");
ofstream out ("transport.out");

int v[16001];
int n,k;
long long sum;

bool verif (int cant)
{
  int sum=0,i,zile=1;
  for (i=1;i<=n;i++)
  {
    if (sum+v[i]<=cant)
        sum+=v[i];
    else if (v[i]>cant)
        return 0;
    else if (sum+v[i]>cant)
        zile++,sum=v[i];
  }
  if (zile<=k)
    return 1;
  return 0;
}

void cautare ()
{
  int pos=0;
  for (int msk=1<<20;msk;msk/=2)
    if (pos+msk<=sum&&verif(pos+msk))
       pos+=msk;
  while (verif(pos))
    pos--;
  pos++;
  out<<pos;
}

int main()
{
    in>>n>>k;
    for (int i=1;i<=n;i++)
       in>>v[i],sum+=v[i];
    cautare();
    return 0;
}