Cod sursa(job #2675421)

Utilizator David861Retegan David David861 Data 21 noiembrie 2020 17:26:23
Problema Transport Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
#define int_min -100001

using namespace std;

ifstream f("transport.in");
ofstream g("transport.out");

int n, k, mxs, s, st, dr, mj, q, cmj;

int main() {

    f >> n >> k;
    mxs = int_min;
    int v[n + 1];

    for (int i = 1; i <= n; i++) {
        f >> v[i];
        s += v[i];
        if (v[i] > mxs)
            mxs = v[i];
    }

    st = mxs;
    dr = s;
    mj = (st + dr)/2;

    while (st != mj && dr != mj) {
        cmj = mj;
        q = 0;
        for (int j = 1; j <=n; j++) {
            if (v[j] < cmj) {
                cmj -= v[j];
            } else {
                q ++;
                cmj = mj;
                cmj -= v[j];
            }
        }
        if (q < k)
            dr = mj;
        else
            st = mj;
        mj = (st + dr)/2;
    }

    g << mj;

    return 0;
}