Submission #1001705

#TimeUsernameProblemLanguageResultExecution timeMemory
1001705vjudge1Bank (IZhO14_bank)C++17
71 / 100
1004 ms14672 KiB
#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) ; 
    }
    if(n == 1) {
        cout << (g[a[1]].size() ? "YES" : "NO") ; return ; 
    }
    for(auto & mask : g[a[1]]) dp[1][mask] = true ; 
    for(ii i = 2 ; i <= n ; i ++ ) {
        bool ok = false ; 
        for(auto & nmask : g[Pre[i]]) {
            for(auto & mask : g[Pre[i - 1]]) {
                if((nmask | mask) == nmask && !dp[i - 1][nmask & mask]) continue ; 
                ii tmp = nmask ^ mask ; 
                if(a[i] == tab[tmp]) {
                    dp[i][nmask] = true ; break ; 
                }
            }
            if(dp[i][nmask]) ok = true ; 
            if(i == n && dp[n][nmask]) {
                cout << "YES" << endl ; return ; 
            }
        }
        if(!ok) break ; 
    }
    cout << "NO" ; 
}
int main(){
    Faster
    T ;
}
                    //////    //    //  //    //  //////
                    //        //   //   //    //      //
                    //////    //////      ////      //
                        //    //  //      //      //
                    //////    //   //    //       ////////
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...