Cod sursa(job #2297035)

Utilizator radubigColtos Radu radubig Data 5 decembrie 2018 10:50:09
Problema Transport Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#define lim 16000
using namespace std;
ifstream in("transport.in");
ofstream out("transport.out");
int a[lim+5],n,k,st,dr,mij,c,s;
int verif(int x)
{
    int cont=0, sum=0;
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]>x)
        {
            cont++;
            sum=0;
        }
        sum+=a[i];
    }
    return cont+1;
}
int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++)
    {
        in>>a[i];
        s+=a[i];
    }
    st=1;
    dr=s;
    c=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(verif(mij)>k)
            st=mij+1;
        else
        {
            c=mij;
            dr=mij-1;
        }
    }
    out<<c;
    return 0;
}