Submission #730315

#	Time	Username	Problem	Language	Result	Execution time	Memory
730315		Macker	Bank (IZhO14_bank)	C++17	100 / 100	112 ms	8516 KiB

bank

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <math.h>
#include <tuple>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <climits>
#include <fstream>
#include <cassert>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

int main()
{
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for (auto& i : p) cin >> i;
    vector<int> b(m);
    for (auto& i : b) cin >> i;

    vector<pair<int, int>> dp((1 << m), {-1, -1});

    dp[0] = { 0, p[0] };
    for (int i = 1; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if (!(i & (1 << j)))continue;
            int li = i ^ (1 << j);
            int k = dp[li].first, rem = dp[li].second;
            if (k == -1)continue;
            if (rem > b[j]) {
                rem -= b[j];
                dp[i] = { k, rem };
            }
            else if (rem == b[j]) {
                k++;
                if (k == p.size()) {
                    cout << "YES" << endl;
                    return 0;
                }
                rem = p[k];
                dp[i] = { k, rem };
            }
        }
    }
    cout << "NO" << endl;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 if (k == p.size()) {
      |                     ~~^~~~~~~~~~~

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