Cod sursa(job #981391)

Utilizator ionut_ungureanuUngureanu Vladut Ionut ionut_ungureanu Data 6 august 2013 23:42:04
Problema Transport Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#define FIN "transport.in","r",stdin
#define FOUT "transport.out","w",stdout

using namespace std;

int n,k,a[16005],i;
long long st,dr,mid,nr,sol;
long long check(long long max_capacity,long long capacity, int vf)
{
    if(!vf)return 1;
    if(a[vf]>max_capacity)return 100+check(max_capacity,capacity,0);
    if(capacity+a[vf]<=max_capacity) return check(max_capacity,capacity+a[vf],vf-1);
    return 1+check(max_capacity,0,vf);
}

int main()
{
    freopen(FIN);
    freopen(FOUT);

    scanf("%d %d",&n,&k);

    for(i=1;i<=n;i++)
        scanf("%d",&a[i]),dr+=a[i];

    dr*=2;
    st=1;
    sol=-1;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        nr=check(mid,0,n);
        if(nr<=k)dr=mid-1,sol=mid;
        else st=mid+1;
    }



    printf("%lld",sol);

    return 0;
}