제출 #1096083

#제출 시각아이디문제언어결과실행 시간메모리
1096083JohnnyVenturas은행 (IZhO14_bank)C++17
0 / 100
0 ms440 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> salaries(n), bills(m);

	for(int i = 0; i < n; ++i) {
		cin >> salaries[i];
	}

	for(int i = 0; i < m; ++i) {
		cin >> bills[i];
	
	}

    vector<int> dp(1 << n), last_value(1 << n);

    dp[0] = -1;
    last_value[0] = 0;

    for (int s = 0; s < (1 << n); ++s) {
        for (int j = 0; j < n; ++j) {
            if (!((1 << j) & s))
                continue;
            int prev_set = (1 << j) ^ s;

            int last_pos = dp[prev_set];

            if (dp[s] == n - 1 || last_pos == n - 1) {
                cout << "YES\n";
                return 0;
            }


			if(salaries[last_pos + 1] == bills[j] + last_value[prev_set]) {
				if(dp[prev_set] + 1 >= dp[s]) {
					last_value[s] = 0;
				}
				dp[s] = max(dp[s], dp[prev_set] + 1);
				continue;
			}

			last_value[s] = last_value[prev_set] + bills[j];
			
        }
    }

	cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...