Submission #1198373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198373		KindaGoodGames	Bank (IZhO14_bank)	C++20	71 / 100	89 ms	16840 KiB

bank

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int,int>
#define tiii tuple<int,int,int>
//#define bs bitset<1001>

using namespace std;


int32_t main(){
    //bs nothing;
    int n,m;
    cin >> n >> m;
    vector<int> sal(n),val(m);

    for(int i = 0; i < n; i++){
        cin >> sal[i];
    }
    for(int i = 0; i < m; i++){
        cin >> val[i];
    }

    int p2 = (1<<m);

    vector<int> dp(p2,-1);
    //vector<bs> left(p2);
    vector<int> left(p2,sal[0]);
    dp[0] = 0;
    left[0] =sal[0];
    bool early = false;
    
    for(int k = 1; k < p2; k++){
        if(early) break;
        for(int i = 0; i < m; i++){
            if(dp[k] >= n) {
                early = true;
                break;
            }
            int cur = (1 << i);
            if(k & cur){
                bool pos = left[k-cur] == val[i];
                  

                if(pos && dp[k-cur]+1 > dp[k]){
                    dp[k] = dp[k-cur]+1;
                    if(dp[k] >= n) break;
                    left[k] = sal[dp[k]]; 
                }else if(dp[k-cur] > dp[k]){
                    dp[k] = dp[k-cur];
                    left[k] = left[k-cur];
                    if(left[k-cur]-val[i] >= 0)left[k]-=val[i]; 
                }
                // else if(dp[k-cur] == dp[k]){
                //     if(left[k-cur]-val[i] >= 0)left[k] = min(left[k] ,left[k-cur]-val[i]); 
                // }
            }
        }
    }

    if(dp[p2-1] == n ||early){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

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