oj.uz

답안 #679286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679286 2023-01-08T02:00:45 Z Hacv16 은행 (IZhO14_bank) C++17
0 / 100
 103 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
const int MAX = 22;
const int MAXM = 50005;
const int INF = 0x3f3f3f3f;
 
int n, m, a[MAX], b[MAX];
int dp[MAX][1 << MAX];
vector<int> g[MAXM];

bool solve(int i, int mask){ //current index, who I have already used
    if(dp[i][mask] != -1) return dp[i][mask];
    if(i == n + 1) return true;

    int targ = a[i], resp = 0;

    for(auto sub : g[targ]){
        if((sub & mask)) continue;
        resp |= solve(i + 1, mask | sub);
    }

    return dp[i][mask] = resp;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
 
    for(int mask = 0; mask < (1 << m); mask++){
        int cur = 0;

        for(int i = 0; i < m; i++)
            if(mask & (1 << i)) cur += b[i];

        g[cur].emplace_back(mask);
    }

    memset(dp, -1, sizeof(dp));
 
    cout << (solve(1, 0) ? "YES" : "NO") << '\n';
 
    return 0;
}

Compilation message

bank.cpp: In function 'bool solve(int, int)':
bank.cpp:26:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |     return dp[i][mask] = resp;
      |            ~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 102 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 103 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -