Cod sursa(job #2638944)

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