제출 #1001670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001670		vjudge1	Bank (IZhO14_bank)	C++17	19 / 100	65 ms	12184 KiB

bank

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ii int
#define pb push_back
#define fi first
#define se second
#define Op operator
#define bp __builtin_popcount
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define TT ll tt;cin>>tt;while(tt--){Test_Case();}
#define T Test_Case() ;
using namespace std;
const ii N = 2e5 , M = 1e6 , mod = 1e9 + 7 , Ones = 1 , Zero = 0;
const ll oo = 1e18 ;
ii tab[1 << 21] , Pre[25] , a[21] , b[21];
bool dp[21][1 << 21] ;
vector<ii> g[2000 * 20 + 5] ;   
void Test_Case(){
    ii n , m ; cin >> n >> m ; 
    for(ii i = 1 ; i <= n ; i ++ ) {
        cin >> a[i] ; Pre[i] = Pre[i - 1] + a[i] ; 
    }
    for(ii i = 1 ; i <= m ; i ++ ) {
        cin >> b[i] ; 
    }
    for(ii mask = 1 ; mask < (1 << m) ; mask ++ ) {
        for(ii i = 0 ; i < m ; i ++ ) {
            if((mask >> i) & 1) {
                tab[mask] += b[i + 1] ; 
            }
        }
        g[tab[mask]].pb(mask) ; 
    }
    for(auto & mask : g[a[1]]) dp[1][mask] = true ; 
    for(ii i = 2 ; i <= n ; i ++ ) {
        for(auto & nmask : g[Pre[i]]) {
            for(auto & mask : g[Pre[i - 1]]) {
                if(!(nmask & mask) || !dp[i - 1][mask]) continue ; 
                ii tmp = nmask ^ mask ; 
                if(a[i] == tab[tmp]) {
                    dp[i][nmask] = true ; break ; 
                }
            }
            if(dp[i][nmask]) break ; 
        }
    }
    for(ii mask = 1 ; mask < (1 << m) ; mask ++ ) {
        if(dp[n][mask]) {
            cout << "YES" ; return ; 
        }
    }
    cout << "NO" ; 
}
int main(){
    Faster
    T ;
}
                    //////    //    //  //    //  //////
                    //        //   //   //    //      //
                    //////    //////      ////      //
                        //    //  //      //      //
                    //////    //   //    //       ////////

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