Submission #1209394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209394		starship_666	은행 (IZhO14_bank)	C++20	100 / 100	150 ms	16712 KiB

bank

///////////////////////////////////////////
//                                       //
//     CODE BY THE phantomstar3.14       //
//                                       //
///////////////////////////////////////////


#include <bits/stdc++.h>
using namespace std;

#define int long long int
#define ull unsigned long long
 
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=1e9+7;

void solve() 
{
    int n,m;
    cin>>n>>m;
    vector<int> a(n,0), b(m,0);
    for(int i=0; i<n; i++)  cin>>a[i];
    for(int i=0; i<m; i++)  cin>>b[i];
    vector<pair<int,int>> dp((1ll<<m), {-1e18, -1e18});
    dp[0]={0,0}; // how many, left
    for(int i=0; i<(1ll<<m); i++)
    {
        for(int j=0; j<m; j++)
        {
            if((1ll<<j)&i == 0) continue;
            int subset=(1ll<<j) ^ i;
            int count=dp[subset].first;
            int left=dp[subset].second;
            if(count==-1e18 or left==-1e18) continue;
            if(count==n)
            {
                cout<<"YES\n";
                return;
            }
            if(left + b[j] == a[count])
                dp[i]={count+1, 0};
            else if (left+b[j] < a[count])
                dp[i]=max(dp[i], {count, left+b[j]});
        }
    }
    for(int i=0; i<(1ll<<m); i++)
    {
        int count=dp[i].first;
        if(count==n)
        {
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
}
 
int32_t main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    auto begin = std::chrono::high_resolution_clock::now();
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    int t=1;
    //cin >> t;
    
    while (t--) 
    {
        solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

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