제출 #516602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516602		Be_dos	은행 (IZhO14_bank)	C++17	100 / 100	598 ms	28168 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];
    int32_t total_target = 0;
    bool** exists_submask = new bool*[m + 1];
    for(int32_t i = 0; i < m + 1; i++)
        exists_submask[i] = new bool[1 << m];
    for(int32_t i = 0; i < n; i++) {
        for(int32_t j = 0; j < 1 << m; j++)
            exists_submask[m][j] = dp[j];
        for(int32_t j = m - 1; j >= 0; j--)
            for(int32_t k = 0; k < (1 << m); k++)
                exists_submask[j][k] = exists_submask[j + 1][k] || ((k & (1 << j)) > 0 && exists_submask[j + 1][k ^ (1 << j)]);

        total_target += arr[i];
        for(int32_t j = 0; j < (1 << m); j++) {
            dp2[j] = false;
            if(subset_sums[j] != total_target)
                continue;

            dp2[j] = exists_submask[0][j];
        }
        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: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29