제출 #1232631

#제출 시각아이디문제언어결과실행 시간메모리
1232631naelwb은행 (IZhO14_bank)C++20
100 / 100
197 ms57860 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define ti3 tuple<int, int, int>
#define int long long
#define mp make_pair
#define ld long double
const int MOD = 1e9+7;
const int INF = 1e18;
const int mxn = 1e5+50;
inline int tot(int a, int b){return (a+b)%MOD;}
inline int sub(int a, int b){return (a+MOD-b)%MOD;}
inline int mul(int a, int b){return (a%MOD*b%MOD)%MOD;}
inline int expo(int a, int b){int res=1; while(b>0){if(b&1)res=mul(res,a); a=mul(a,a); b>>=1;} return res;}
inline int inverse(int a){a%=MOD; return expo(a,MOD-2);}
void chmx(int &a, int b){a = max(a,b);}
void chmn(int &a, int b){a = min(a,b);}

void solve(){
    int n, m; cin >> n >> m;
    int a[n+1], b[m+1];
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= m; i++)cin>>b[i];
    vector<vector<int>> dp(1<<20, vector<int>(2, -1));
    dp[0][0] = 0;
    dp[0][1] = 0;
    for(int i = 0; i < (1 << m); i++){
        for(int j = 0; j < 20; j++){
            if(i&(1 << j) == 0) continue;
            int bfr = i^(1 << j);
            if(dp[bfr][0] == -1) continue;

            int need = a[dp[bfr][0]+1];
            int have = b[j+1] + dp[bfr][1];
            if(need > have){
                dp[i][1] = have;
                dp[i][0] = dp[bfr][0];
            } else if(need == have){
                dp[i][1] = 0;
                dp[i][0] = dp[bfr][0] + 1;
            }
            if(dp[i][0] == n){
                cout << "YES\n"; return;
            }
        }
    } cout << "NO\n";
}

int32_t main(){
    fastio;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...