제출 #516589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516589		Be_dos	은행 (IZhO14_bank)	C++17	52 / 100	1090 ms	5864 KiB

bank

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int main() {
    int32_t n, m;
    std::cin >> n >> m;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    int32_t* arr2 = new int32_t[m];
    for(int32_t i = 0; i < m; i++)
        std::cin >> arr2[i];
    int32_t* subset_sums = new int32_t[1 << m];
    subset_sums[0] = 0;
    for(int32_t i = 1; i < (1 << m); i++) {
        int32_t bit = __builtin_ctz(i);
        subset_sums[i] = subset_sums[i ^ (1 << bit)] + arr2[bit];
    }

    bool* dp = new bool[1 << m];
    for(int32_t i = 0; i < (1 << m); i++)
        dp[i] = false;
    dp[0] = true;
    bool* dp2 = new bool[1 << m];
    for(int32_t i = 0; i < n; i++) {
        for(int32_t j = 0; j < (1 << m); j++) {
            dp2[j] = false;
            for(int32_t k = j; k > 0; k = (k - 1) & j)
                dp2[j] |= dp[j ^ k] && (subset_sums[k] == arr[i]);
        }
        bool* tmp = dp;
        dp = dp2;
        dp2 = tmp;
    }

    for(int32_t j = 0; j < (1 << m); j++)
        if(dp[j]) {
            std::cout << "YES";
            return 0;
        }
    std::cout << "NO";
    return 0;
}
         

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