Submission #850253

#	Time	Username	Problem	Language	Result	Execution time	Memory
850253		PhamGiaKhanh	Bank (IZhO14_bank)	C++14	100 / 100	96 ms	9660 KiB

bank

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define setpre(n) setprecision(n) << fixed
typedef long long ll;
const int INF = 1e9;
const int maxN = 20;
const int maxM = 1e2 + 7;
const int MOD = 1e9 + 7;
using namespace std;
int a[maxN], b[maxN];
bool money[1 << maxN];
pair<int, int> dp[1 << maxN];
main()
{
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    dp[0] = mp(0, 0);
    money[0] = 1;
    for(int i = 0; i < (1 << m); i++){
        for(int j = 0; j < m; j++){
            if(i & (1 << j)){
                if(!money[i ^ (1 << j)]) continue;
                pair<int, int> cur = dp[i ^ (1 << j)];
                if(cur.fi < n && cur.se + b[j] < a[cur.fi]){
                    cur.se += b[j];
                    dp[i] = cur;
                    money[i] = 1;
                }
                else if(cur.fi < n && cur.se + b[j] == a[cur.fi]){
                    cur.fi++;
                    cur.se = 0;
                    dp[i] = cur;
                    money[i] = 1;
                }
            }
        }
        if(money[i] && dp[i].fi >= n){
            cout << "YES" << '\n';
            return 0;
        }
    }
    cout << "NO" << '\n';
    return 0;
}

Compilation message (stderr)

bank.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~

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