Cod sursa(job #2638936)

Utilizator vladdobro07vladdd vladdobro07 Data 30 iulie 2020 17:18:16
Problema Transport Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
int v[16001];
int main() {
        int n,k,minn,maxx,x,s=0,mid,sk=0,last;
        cin>>n>>k;
        for(int i=1; i<=n; i++) {
                cin>>x;
                v[i]=x;
                s+=x;
        }
        maxx=s;
        minn=s/k;
        while(minn<maxx) {
                mid=(maxx+minn)/2;
                int c=1;
                sk=0;
                for(int i=1;i<=n;i++){
                        if(v[i]+sk<=mid)
                                sk+=v[i];
                        else {
                                sk=v[i];
                                c++;
                        }
                }
                if(c<=k) {
                        last=mid;
                        maxx=mid;
                } else
                        minn=mid+1;
        }
        cout<<last;
        return 0;
}