Cod sursa(job #2199566)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 28 aprilie 2018 11:58:58
Problema Zebughil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#define c first
#define ramas second
#include <fstream>
#include <cstring>
#include <bitset>

using namespace std;

ifstream fin ("zebughil.in");
ofstream fout ("zebughil.out");

const int Dim = 18,Inf = 0x3f3f3f3f;
pair <  int , int > D[1 << Dim];
int n,g,A[Dim];

void Dynamic();

int main() {

	for ( int t = 1; t <= 3; ++t) {
	fin >> n >> g;
	for ( int i = 1; i <= n; ++i)
		fin >> A[i];
	memset(D,0,sizeof(D));
	Dynamic();
	fout << D[ (1 << n) - 1].c << "\n";
	}
}

void Dynamic(){

    for (int i = 0; i < 1 << n; ++i)
        D[i] = {Inf,0};
    D[0] = {0,0};
	for(int i = 0; i < 1 << n; ++i)  {
		for ( int j = 1; j <= n; ++j) {
			if ( (( 1 << (j - 1) ) & i) == (1 << (j-1)) )
				continue;
			if ( D[i].ramas >= A[j] ) {
			    if (D[(i | ( 1 << (j - 1) ))].c > D[i].c)
                    D[(i | ( 1 << (j - 1) )) ] = {D[i].c,D[i].ramas - A[j]};
                if (D[(i | ( 1 << (j - 1) ))].c ==  D[i].c and
                    D[(i | ( 1 << (j - 1) ))].ramas < D[i].ramas- A[j])
                        D[(i | ( 1 << (j - 1) )) ] = {D[i].c,D[i].ramas - A[j]};
				}
			else
                if (D[(i | ( 1 << ( j - 1)))].c > D[i].c + 1)
                    D[ (i | ( 1 << ( j - 1))) ] = {D[i].c + 1, g - A[j]};
            else if (D[(i | ( 1 << ( j - 1)))].c ==  D[i].c + 1
                    and D[(i | ( 1 << ( j - 1)))].ramas < g - A[j])
                          D[ (i | ( 1 << ( j - 1))) ] = {D[i].c + 1, g - A[j]};
			}
		}
}