Submission #501439

#	Time	Username	Problem	Language	Result	Execution time	Memory
501439		LucaIlie	Bank (IZhO14_bank)	C++17	100 / 100	452 ms	54700 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 );
        }
    }

    for ( i = 0; i < sol[0].size(); i++ )
        sePoate[0][sol[0][i]] = 1;
    for ( i = 1; i < m; i++ ) {
        for ( mask = 0; mask < (1 << n); mask++ ) {
            if ( sePoate[i - 1][mask] ) {
                for ( j = 0; j < sol[i].size(); j++ ) {
                    if ( (mask & sol[i][j]) == 0 )
                        sePoate[i][mask + sol[i][j]] = 1;
                }
            }
        }
    }

    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:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for ( i = 0; i < sol[0].size(); i++ )
      |                  ~~^~~~~~~~~~~~~~~
bank.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 for ( j = 0; j < sol[i].size(); j++ ) {
      |                              ~~^~~~~~~~~~~~~~~

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