Cod sursa(job #2807688)

Utilizator DavidNenciuDavid Nenciu DavidNenciu Data 24 noiembrie 2021 09:17:57
Problema Transport Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>

using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
int v[16001];
int main()
{
    int max=-1,s=0,n,i,aux,st,dr,mij,nr1,k,nr,afi;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        cin>>v[i];
        s+=v[i];
        if(max<v[i])
            max=v[i];
    }
    st=max;
    dr=s;
    s=0;
    while(st<=dr){
        mij=(st+dr)/2;
        s=mij;
        nr=0;
        for(i=1;i<=n;i++){
            if(s-v[i]<0){
                s=mij;
                nr++;
            }
            s-=v[i];
        }
        nr++;
        if(nr>k)
            st=mij+1;
     else
        if(nr<k){
            dr=mij-1;
            afi=mij;
        }
    }
    cout<<afi;
    return 0;
}