제출 #1122964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122964		Mamikonm1	은행 (IZhO14_bank)	C++17	100 / 100	270 ms	8872 KiB

bank

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <string>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
using db = double;
const float pi = 3.14159265359;
#define V vector
#define VI V<int>
#define P pair<int,int>
#define rep(i, a, b, step) for (int i = int(a); i <= int(b); i += step)
#define repl(i,a,b,step) for (int i = int(a); i >= int(b); i -= step)
#define prime(n) [](ll x) { for (ll i = 2; i * i <= x; ++i) if (x % i == 0) return false; return x > 1; }(n)
#define printall(container, ch) for (const auto& elem : container) { std::cout << elem << ch; } std::cout << std::endl;
#define lcm(a, b) ((a * b) / gcd(a, b))
#define sn << '\n'
#define ed << endl
#define sz size()
#define print cout <<
#define debug(x) print #x << " = " << x sn;
#define mpII map<int,int>
#define mine min_element
#define maxe max_element
#define all(v) begin(v), end(v)
#define txt freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
#define MEX(a) [](VI a){set<int>elem;for(auto&i:a)elem.insert(i);int ret=0;while(elem.count(ret))ret++;return ret;}(a)
#define pb push_back    
#define pq priority_queue
#define rev reverse
#define nuyn(a) a.erase(unique(all(a)), end(a))
#define nx next_permutation     
#define pk pop_back()
#define START print "Start" sn
#define END print "End" sn
#define ff first
#define ss second   
#define ts to_string        
#define ub upper_bound  
#define mk make_pair 
#define lb lower_bound          
#define testcase int t;cin>>t;while(t--)solution();
const int N = 1e3;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, sum;
    cin >> n >> m;
    VI a(n), b(m);
    V<V<bool>>vis(n, V<bool>(1 << m, 1));
    V<VI>graph(N + 1);
    for (auto& i : a)cin >> i;
    for (auto& i : b)cin >> i;
    rep(i, 1, (1 << m) - 1, 1) {
        sum = 0;
        rep(j, 0, m - 1, 1)
            sum += ((i & (1 << j)) > 0) * b[j];
        if (sum <= N)
            graph[sum].pb(i);
    }
    auto dfs = [&](auto&& dfs, int mask, int u)->bool {
        if (u == n - 1)return 1;
        bool ret = 0;
        if (!vis[u][mask])return 0;
        vis[u][mask] = 0;
        for (auto& i : graph[a[u + 1]])
            if (!(mask & i))
                ret |= dfs(dfs, mask + i, u + 1);
        return ret;
        };
    bool ans = 0;
    for (auto& i : graph[a[0]])
        ans |= dfs(dfs, i, 0);
    print(ans ? "YES" : "NO")sn;
}

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