Submission #1262759

#TimeUsernameProblemLanguageResultExecution timeMemory
1262759gmysBank (IZhO14_bank)C++17
19 / 100
76 ms8516 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define oo 1e18
const int MM = 1e6+7;
int n,m,a[MM],b[MM];
pair<int,int> dp[1 << 20];
// .fi = so nguoi co the tra luong tinh den hien tai
// .se = so tien dang co
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 0;i < m;i++) cin >> b[i];

    int id = 1;
    for(int mask = 0;mask < (1 << m);mask++) {
        for(int i = 0;i < m;i++) {
            if(mask >> i & 1) {
                int nums = dp[mask].fi, cur_coin = dp[mask].se;
                if(cur_coin + b[i] == a[id]) {
                    dp[mask] = max(dp[mask],{nums+1,0});
                    id++;
                }
                else if(cur_coin + b[i] < a[id]) 
                    dp[mask] = {nums,cur_coin + b[i]};
            }
        }
    }
    for(int mask = 0;mask < (1 << m);mask++) {
        if(dp[mask] == make_pair(n,0)) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...