Submission #1328497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328497		hegoplay	Bank (IZhO14_bank)	C++20	71 / 100	1101 ms	195660 KiB

bank

/*
                                                                                                        -
                                                             +=
                                                           @@@@@%
                                                         +@@@@@@+
                                                      %@@@@@#%
                                                     @@@@@@@@=:
                       +******************         =@@@@@@@@@%         =***********#*******+
                    %@@@@@@@@@@@@@@@@@@@@=         @@@@@@@@@@%      #@@@@@@@@@@@@@@@@@@@@@@
                  +@@@@@@@@@@@@@@@@@@@@@+        +@@#@@@@@@@@%     @@@@@@@@@@@@@@@@@@@@@@@=
                 +@@@@%                         *@@%@@@@@@@@@=    %@@@%
                 @@@@@#                        *@@@@@@@@@@@@#    #@@@@@
                %@@@@%                        +@@@@@@@@@@@@%     @@@@@@@@@@@@@@@@@@@@%
               #@@@@@                        =#+@@@@@@@@#@%      =@@@@@@@@@@@@@@@@@@@@*
              +@@@@@+                         #@@@@@@%                          =@@@@@=
             =@@@@@*                        #@@@@@@#                            @@@@@*
             #@@@@@@@@@@@@@@@@@@@@@       +@@@@@@#           *@@@@@@@@@@@@@@@@@@@@@@#
             +@@@@@@@@@@@@@@@@@@@@=      %@@@@@%            +@@@@@@@@@@@@@@@@@@@@@@+
               +*#************##*      =@@@@@#+             ###**##**#*******##*+
                                      =@@@@@@%
                                        +**  =+=
                                    Michael Jackson peeks

    "Nothing is hard to understand, you just didn't get it."
    @author: MahK17
*/
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define sz(x) (int)(x).size()
#define el "\n"
typedef long long ll;
typedef long double ld;
#define int long long
using namespace __gnu_pbds;
using namespace std;

void setIO(string name = "")
{
    if (sz(name))
    {
        freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
long long binpow(long long a, long long b, long long m)
{
    a %= m;
    long long res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

const int MOD = 1e9 + 7;
const int MOD9 = 998244353LL;

const int MAXN = 20;

ll fac[MAXN + 1];
ll inv[MAXN + 1];

void factorial()
{
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
}

void inverses()
{
    inv[MAXN] = binpow(fac[MAXN], MOD - 2, MOD);
    for (int i = MAXN; i >= 1; i--)
    {
        inv[i - 1] = inv[i] * i % MOD;
    }
}

ll combinations(int n, int r)
{
    if (r < 0 || r > n)
        return 0;
    if (r == 0 || r == n)
        return 1;

    // Tận dụng tính chất đối xứng để giảm số bước lặp
    if (r > n - r)
        r = n - r;

    ll ans = 1;
    for (int i = 1; i <= r; i++)
    {
        ans = ans * (n - i + 1) / i;
    }
    return ans;
}
// last, count
pair<int, map<int,int>> dp[1 << MAXN];

void solve(int t)
{
    int n,m;
    cin >> n >> m;
    int a[n];
    map<int,int> mp;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int b[m];
    for(int i = 0 ; i < m;i++){
        cin >> b[i]; 

    }
    for(int i = 0 ; i < (1 << m);i++){
        dp[i].first = inf;
        dp[i].second.clear();
    }
    dp[0] = {0,{}};
    for(int mask = 0 ; mask < (1 << m);mask++){
        for(int i = 0 ; i < m;i++){
            if(mask & (1 << i)) continue;
            int last = dp[mask].first;
            last+= b[i];
            auto tempMp = dp[mask].second;
            if (mp.count(last) && tempMp[last] < mp[last]){
                tempMp[last]++;
                dp[mask | (1 << i)] = min(dp[mask | (1 << i)], {0,tempMp});
            }
            else {
                dp[mask | (1 << i)] = min(dp[mask | (1 << i)], {last,tempMp});
            }
        }
    }
    int cnt = 0;
    for(auto &x : dp[(1 << m) - 1].second){
        cnt+= x.second;
    }
    for(auto &x : mp){
        cnt-= x.second;
    }
    if (cnt == 0) yes
    else no;
}

signed main()
{
    // factorial();
    // inverses();
    ios ::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve(i);
    }
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'void setIO(std::string)':
bank.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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