Cod sursa(job #1864347)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 31 ianuarie 2017 18:32:35
Problema Transport Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#define LL long long
#define DM 16000
using namespace std;

ifstream fi ("transport.in");
ofstream fo ("transport.out");

LL s[DM], n, k, suma, mx;

bool functie (LL i)
{
    LL c = 1, total = 0;
    for (int j = 0; j < n; ++j)
    {
        if (total + s[j] > i)
        {
            ++c;
            total = 0;
        }
        total+=s[j];
    }
    if (c > k)
        return 0;
    return 1;
}

int binar (LL mx, LL suma, LL k)
{
    int ls = mx, ld = suma, mid;
    while (ls <= ld)
    {
        mid = (ls + ld)/2;

        if (!functie(mid))
            ls = mid + 1;
        else
            ld = mid - 1;
    }
    fo << mid;
    return mid;
}

int main()
{
    fi >> n >> k;
    for (LL i = 0; i <= n; ++i)
    {
        fi >> s[i];
        suma+=s[i];
        if (s[i] > mx)
            mx = s[i];
    }
    binar (mx, suma, k);
    return 0;
}