Submission #899386

#	Time	Username	Problem	Language	Result	Execution time	Memory
899386		Karoot	Bank (IZhO14_bank)	C++17	100 / 100	451 ms	82708 KiB

bank

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

vector<int> ways[21];
int mem[21][1048577];
int n, m;

int dp(int index, int used){
    if (index == n)return 0;
    if (mem[index][used] != -1)return mem[index][used];
    int best = 0;
    for (int x : ways[index]){
        if ((x | used) == (x ^ used))best = max(best, dp(index+1, used | x)+1);
    }
    return mem[index][used] = best;
}

int main(){
    scoobydoobydoo();
    cin >> n >> m;
    vector<int> salaries(n);
    vector<int> notes(m);
    for (int i = 0; i < n; i++)cin >> salaries[i];
    for (int i = 0; i < m; i++)cin >> notes[i];

    for (int j = 0; j < (1<<m); j++){
        int sum = 0;
        for (int x = 0; x < m; x++){
            if ((1<<x)&j)sum += notes[x];
        }
        for (int i = 0; i < n; i++){
            if (salaries[i] == sum)ways[i].push_back(j);
            mem[i][j] = -1;
        }
    }

    if (dp(0, 0) == n)cout << "YES" << endl;
    else cout << "NO" << endl;


    return 0;
}

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