Submission #1084687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084687		chaoslong	Bank (IZhO14_bank)	C++14	100 / 100	388 ms	221784 KiB

bank

// Calm down.
// Think three times, code twice.
#include "bits/stdc++.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int N = 2e6 + 5;
const int mod = 1e9 + 7; // 998244353
const ll oo = 1e18;

int n, m, a[N], b[N], dp[N][25];
bool check[N][25];

void to_nho_cau() {
    cin >> n >> m;
    forr(i, 1, n) cin >> a[i];
    forr(i, 1, m) cin >> b[i];
    //xét mask của tờ tiền, với mỗi mask duyệt từng tờ và duyệt thêm i là mức lương nó đã được giải quyết tới i và có tổng là k
    memset(dp, 63, sizeof dp);
    dp[0][1] = 0;
    forr(i, 0, mask(m) - 1) {
        forr(j, 0, m-1)
            if(bit(i, j)) {
                forr(k, 1, n) {
                    int cost = (dp[i ^ (1LL << j)][k] + b[j+1] <= a[k]) ? 1: 0;
//                    cout << i << " " << j << " " << k << " " << (i ^ (1LL << j)) << " " << dp[i ^ (1LL << j)][k] << " " << cost << "\n";
                    if(cost) {
                        dp[i][k] = dp[i ^ (1LL << j)][k] + b[j+1];
                        if(dp[i][k] == a[k]) {
    //                        cout << i << " " << j << " " << k << " " << dp[i][k] << " " << a[k] << "\n";
                            dp[i][k+1] = 0;
                            check[i][k] = 1;
                        }
                    }
                }
            }
    }
    forr(i, 0, mask(m) - 1) {
        if(check[i][n]) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef LOCAL
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) to_nho_cau();
}
/*
1.self check:
2.long long
3.size of array
4.code for testing
5.initializing
6.modulo number
*/
/**
  ∧__∧
（｀•ω• )づ__∧
（つ　 /( •ω•。)
  しーＪ (nnノ) pat pat
**/
/**  /\_/\
*   (= ._.)
*   / >☕ \>💻
**/

Compilation message (stderr)

bank.cpp:88:9: warning: "/*" within comment [-Wcomment]
   88 | /**  /\_/\
      |

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