Cod sursa(job #1907027)

Utilizator robx12lnLinca Robert robx12ln Data 6 martie 2017 17:29:36
Problema Lapte Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<fstream>
#include<cstring>
#define DIM 105
using namespace std;
ifstream fin("lapte.in");
ofstream fout("lapte.out");
int Ca[DIM], Cb[DIM], n, L, st, dr, mid;
int D[DIM][DIM], Nrl[DIM][DIM];

int check( int T ){
    //D[i][j] = cantitatea maxima de lapte B care se poate bea
    //          daca primii i au baut j litri lapte A
    for( int i = 0; i < DIM; i++ ){
        for( int j = 0; j < DIM; j++ ){
            D[i][j] = -( (1<<31) - 1 );
        }
    }
    D[0][0] = 0;
    for( int i = 1; i <= n; i++ ){
        for( int La = 0; La <= T / Ca[i]; La++ ){
            for( int j = 0; j <= L - La; j++ ){
                int Lb = ( T - ( La * Ca[i] ) ) / Cb[i];
                if( D[i][j + La] < D[i - 1][j] + Lb ){
                    D[i][j + La] = D[i - 1][j] + Lb;
                    Nrl[i][j + La] = La;
                }
            }
        }
    }
    if( D[n][L] >= L ){
        return 1;
    }
    return 0;
}

void solve( int i, int j ){
    if( i != 0 ){
        solve( i - 1, j - Nrl[i][j] );
        fout << Nrl[i][j] << " " << D[i][j] - D[i - 1][ j - Nrl[i][j] ] << "\n";
    }
}

int main(){
    fin >> n >> L;
    for( int i = 1; i <= n; i++ ){
        fin >> Ca[i] >> Cb[i];
    }
    st = 1;
    dr = 100;
    while( st <= dr ){
        mid = ( st + dr ) / 2;
        if( check( mid ) == 1 ){
            dr = mid - 1;
        }else{
            st = mid + 1;
        }
    }
    fout << st << "\n";
    check( st );
    solve( n, L );
    return 0;
}