제출 #1257617

#제출 시각아이디문제언어결과실행 시간메모리
1257617_unknown_2010은행 (IZhO14_bank)C++20
100 / 100
75 ms16712 KiB
// #ifndef khos
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef khos
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1e9+7;
const int MAXN=50;
const int inf=1e18;
void solution() {
    int n,m;
    cin >> n >> m;
    vi<int> a(n);
    for(auto &x:a)cin >> x;
    vi<int> b(m);
    for(auto &x:b)cin >> x;
    vi<pair<int,int>> dp((1LL<<m));
    dp[0]={0,0};
    for(int i=1; i<(1LL<<m); i++){
        dp[i]={-1, 0};
        for(int j=0; j<m; j++){
            if(!(i&(1LL<<j)))continue;
            int prev=i^(1LL<<j);
            if(dp[prev].ff==-1)continue;
            int ind=dp[prev].ff;
            int cnt=dp[prev].ss;
            if(b[j]+cnt<a[ind]){
                dp[i].ff=dp[prev].ff;
                dp[i].ss=cnt+b[j];
                break;
            }
            else if(b[j]+cnt==a[ind]){
                dp[i].ff=dp[prev].ff+1;
                dp[i].ss=0;
                break;
            }
        }
    }
    for(int i=0; i<(1LL<<m); i++){
        if(dp[i].ff==n){
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}
int32_t main(){
    clock_t tStart = clock();
    // freopen("movie.in", "r", stdin);
    // freopen("movie.out", "w", stdout);
    #ifdef khos
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
        // cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...