Submission #504310

#	Time	Username	Problem	Language	Result	Execution time	Memory
504310		RandomLB	Bank (IZhO14_bank)	C++17	100 / 100	188 ms	14392 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> point;
typedef tuple<ll, ll, ll> tp;
typedef priority_queue<pll, vector<pll>, greater<pll>> djk;
#define pb push_back
#define ms(a,b) memset(a,b,sizeof(a));
#define maxE(a) *max_element(a, a+sizeof(a)/sizeof(a[0]))
#define minE(a) *min_element(a, a+sizeof(a)/sizeof(a[0]))
#define F first
#define S second
#define siz(a) (int)a.size()
#define len(a) (int)a.length()
#define all(x) (x).begin(), (x).end()
#define bits(x) __builtin_popcount(x)
#define bin(a, x) bitset<a>(x)
#define vvll vector<vector<ll>>
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout << endl;
}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const double pie = 2*acos(0.0);
//------------------------------------------------------------
vector<int> moves[20];
int item[20], val[20], n, m;
bool vis[20][1<<20], dp[20][1<<20];

bool solve(int curr, int mask){
    if (curr == n) return true;
    if (vis[curr][mask]) return dp[curr][mask];
    vis[curr][mask] = true;
    for (int take: moves[curr]){
        //deb(bin(5, mask), bin(5, take));
        if ((mask&take) != take) continue;
        if (solve(curr+1, mask^take)){
            dp[curr][mask] = true;
            break;
        }
    }
    return dp[curr][mask];
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    //freopen("test.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> item[i];
    for (int i = 0; i < m; i++) cin >> val[i];
    for (int mask = 0; mask < 1<<m; mask++){
        int sum = 0;
        for (int i = 0; i < m; i++){
            if (mask & (1<<i)) sum += val[i];
        }
        for (int i = 0; i < n; i++) if (sum == item[i]) moves[i].pb(mask);
    }
    cout << (solve(0, (1<<m)-1)? "YES" : "NO") << "\n";
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

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