Cod sursa(job #1024653)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 8 noiembrie 2013 22:11:30
Problema Transport Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;

ifstream is("transport.in");
ofstream os("transport.out");

int a[16001], n, k;
int ma, sol, s, cnt, saux;

int main()
{
    is >> n >> k;
    for ( int i = 0; i < n; i++ )
    {
        is >> a[i];
        if ( a[i] > ma )
            ma = a[i];
        s += a[i];
    }
    sol = ( ma + s ) / 2;
    while ( cnt != k )
    {
        cnt = 0;
        saux = 0;
        for ( int i = 0; i < n; i++ )
            if ( saux + a[i] <= sol )
                saux += a[i];
            else
            {
                saux = 0;
                cnt++;
            }
        if ( cnt < k )
            sol--;
        else
            if ( cnt > k )
                sol++;
    }
    os << sol;
    is.close();
    os.close();
    return 0;
}