제출 #483542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483542		Yomapeed	은행 (IZhO14_bank)	C++17	100 / 100	176 ms	16832 KiB

bank

#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define printclock cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll B) { return (unsigned ll)rng() % B;}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll _T = 1;
    
    //cin >> _T;
    while (_T--) {
        ll N, M;
        cin >> N >> M;
        vector<ll> a(N), b(M);
        for(int i = 0; i < N; i++) cin >> a[i];
        for(int i = 0; i < M; i++) cin >> b[i];
        vector<ll> pref(N + 1);
        for(int i = 0; i < N; i++){
            pref[i + 1] += pref[i] + a[i];
        }
        vector<ll> sum(1 << M);
        for(int i = 0; i < (1 << M); i++){
            for(int j = 0; j < M; j++){
                if(i & (1 << j)){
                    sum[i] += b[j];
                }
            }
        }
        vector<ll> dp(1 << M, -INF);
        dp[0] = 0;
        for(int mask = 0; mask < (1 << M); mask++){
            ll curr = dp[mask];
            if(curr == -INF){
                continue;
            }
            if(curr == N){
                cout << "YES\n";
                return 0;
            }
            // if(pref[curr + 1] - sum[mask] == a[curr]){
            //     dp[mask] = max(dp[mask], curr + 1);
            // }
            ll m = 0;
            for(int j = 0; j < M; j++){
                if(mask & (1 << j)){
                    continue;
                }
                dp[mask ^ (1 << j)] = max(dp[mask ^ (1 << j)], curr + (pref[curr] - sum[mask ^ (1 << j)] == -a[curr]));
            }
            // for (int s = m; ; s = (s - 1) & m) {
            //     if(sum[s] == a[curr]){
            //         dp[mask ^ s] = max(dp[mask ^ s], curr + 1);
            //     }
                
            //     if (s == 0){
            //         break;
            //     }
            // }
        }
        cout << "NO\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'int main()':
bank.cpp:66:16: warning: unused variable 'm' [-Wunused-variable]
   66 |             ll m = 0;
      |                ^

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