Submission #501438

#	Time	Username	Problem	Language	Result	Execution time	Memory
501438		LucaIlie	Bank (IZhO14_bank)	C++17	71 / 100	1030 ms	7520 KiB

bank

#include <iostream>
#include <vector>

#define MAX_N 20
#define MAX_M 20

using namespace std;

int s[MAX_M], b[MAX_N], sePoate[MAX_M][1 << MAX_N];
vector <int> sol[MAX_M];

int main() {
    int m, n, suma, mask, i, j;

    cin >> m >> n;
    for ( i = 0; i < m; i++ )
        cin >> s[i];
    for ( i = 0; i < n; i++ )
        cin >> b[i];

    for ( mask = 0; mask < (1 << n); mask++ ) {
        suma = 0;
        for ( i = 0; i < n; i++ ) {
            if ( (mask >> i) & 1 )
                suma += b[i];
        }
        for ( i = 0; i < m; i++ ) {
            if ( s[i] == suma )
                sol[i].push_back( mask );
        }
    }

    /*int l
    for ( i = 0; i < m; i++ ) {
        printf( "%d:\n", s[i] );
        for ( j = 0; j < sol[i].size(); j++ ) {
            for ( l = 0; l < n; l++ ) {
                if ( (sol[i][j] >> l) & 1 )
                    printf( "%d ", b[l] );
            }
            printf( "\n" );
        }
        printf( "\n" );
    }*/

    for ( i = 0; i < sol[0].size(); i++ )
        sePoate[0][sol[0][i]] = 1;
    for ( mask = 0; mask < (1 << n); mask++ ) {
        for ( i = 0; i < n; i++ ) {
            if ( (mask >> i) & 1 )
                sePoate[0][mask] |= sePoate[0][mask - (1 << i)];
        }
    }
    for ( i = 1; i < m; i++ ) {
        for ( mask = 0; mask < (1 << n); mask++ ) {
            for ( j = 0; j < sol[i].size(); j++ ) {
                if ( (mask & sol[i][j]) == sol[i][j] )
                    sePoate[i][mask] |= sePoate[i - 1][mask - sol[i][j]];
            }
        }
    }
    /*for ( i = 0; i < m; i++ ) {
        for ( mask = 0; mask < (1 << n); mask++ )
            if ( sePoate[i][mask] )
                printf( "%d ", mask );
        printf( "\n" );
    }*/

    mask = 0;
    while ( mask < (1 << n) && !sePoate[m - 1][mask] )
        mask++;

    if ( mask == (1 << n) )
        cout << "NO";
    else
        cout << "YES";

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for ( i = 0; i < sol[0].size(); i++ )
      |                  ~~^~~~~~~~~~~~~~~
bank.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for ( j = 0; j < sol[i].size(); j++ ) {
      |                          ~~^~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29