제출 #1351777

#제출 시각아이디문제언어결과실행 시간메모리
1351777xorreverse은행 (IZhO14_bank)C++20
100 / 100
110 ms8596 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxN = 25;
int n, m, a[maxN],b[maxN];
int f[(1 << 20)];
int d[(1 << 20)];
bool check[200005];
bool testBit(int x, int k){
    return x & (1 << k);
}
bool g[15][(1 << 10)];
namespace sub2{
    void solve(){
        g[0][0] = 1;

        for (int i = 0; i < n; i ++){
            for (int j = 0; j < (1 << m); j ++){
                if (!g[i][j]) continue;
                for (int k = 0; k < (1 << m); k ++){
                    if (d[k] == a[i + 1] && (j & k) == 0){
                        g[i + 1][j ^ k] = 1;
                    }
                }
            }
        }
        bool ok = 0;
        for (int j = 0; j < (1 << m); j ++){
            if (g[n][j]) ok = 1;
        }
        if (ok) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
namespace sub4{
    void solve(){

        int res = 0;
        for (int i = 1; i <= n; i ++){
            res += a[i];
            check[res] = 1;
           // cout << res << '\n';
        }
        for (int i = 0; i < (1 << m); i ++){
            //cout << d[i] << '\n';
            for (int j = 0; j < m; j ++){
                if (testBit(i, j)) f[i] = max(f[i], f[i ^ (1 << j)]);
            }
            f[i] += check[d[i]];
          // if (i == 0) cout << f[0] << " " << check[d[1]]<< '\n';
        }
        bool ok = 0;
        for (int i = 0; i < (1 << m); i ++){
            ok = max(ok, (f[i] == n));
        }
        if (ok) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++) cin >> b[i];
        for (int i = 0; i < (1 << m); i ++){
            int sum = 0;
            for (int j = 1; j <= m; j ++){
                if (testBit(i, j - 1)) sum += b[j];
            }
            d[i] = sum;
        }
        if (n <= 10 && m <= 10) sub2::solve();
  else sub4::solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...