Submission #1111855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111855		themaver1cks	Bank (IZhO14_bank)	C++14	100 / 100	96 ms	8848 KiB

bank

/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
> love miku so muchhhh <3
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
// var dec
const int maxn = 22;
int n, m;
// ds dec
int a[maxn], b[maxn];
//
namespace sub1
{
    bool condition()
    {
        return (n == 1);
    }
    //
    void solve()
    {
        bool ans = 0;
        for (int mask=1; mask<(1<<m); ++mask)
        {
            int sum = 0;
            for (int j=0; j<m; ++j)
                if (mask & (1<<j)) sum += b[j+1];
            if (sum == a[1])
            {
                ans = 1;
                break;
            }
        }
        cout << (ans ? "YES" : "NO") << el;
    }
}
//
namespace sub2
{
    bool condition()
    {
        return (n <= 10 && m <= 10);
    }
    //
    void solve()
    {
        vector <vector<bool>> dp(n+3, vector<bool>((1<<m)+3, 0));
        dp[0][0] = 1;
        for (int i=1; i<=n; ++i)
        {
            for (int mask=1; mask<(1<<m); ++mask)
            {
                for (int pre_mask=0; pre_mask<(1<<m); ++pre_mask)
                {
                    if (mask & pre_mask) continue;
                    int sum = 0;
                    for (int j=0; j<m; ++j)
                        if (mask & (1<<j)) sum += b[j+1];
                    int cur_mask = (mask | pre_mask);
                    if (sum == a[i]) dp[i][cur_mask] = (dp[i][cur_mask] | dp[i-1][pre_mask]);
                }
            }
        }
        for (int mask=1; mask<(1<<m); ++mask)
        {
            if (dp[n][mask]) return void(cout << "YES" << el);
        }
        cout << "NO" << el;
    }
}
//
namespace sub4
{
    void solve()
    {
        vector <int> covered(1<<m, -1), left_over(1<<m, -1);
        covered[0] = 0; left_over[0] = 0;
        for (int mask=1; mask<(1<<m); ++mask)
        {
            for (int i=0; i<m; ++i)
            {
                if (!(mask & (1<<i))) continue;
                int prev = mask & ~(1<<i);
                if (covered[prev] == -1) continue;

                int amt = left_over[prev] + b[i+1];
                int target = a[covered[prev]+1];

                if (amt < target)
                {
                    covered[mask] = covered[prev];
                    left_over[mask] = amt;
                }
                else if (amt == target)
                {
                    covered[mask] = covered[prev] + 1;
                    left_over[mask] = 0;
                }
            }
            if (covered[mask] == n) return void(cout << "YES" << el);
        }
        cout << "NO" << el;
    }
}
//
void solve()
{
    cin >> n >> m;
    for (int i=1; i<=n; ++i) cin >> a[i];
    for (int i=1; i<=m; ++i) cin >> b[i];
    if (sub1::condition()) sub1::solve();
    else sub4::solve();
}
//
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("lmao.inp", "r"))
    {
        freopen("lmao.inp", "r", stdin);
        freopen("lmao.out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int32_t main()':
bank.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("lmao.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("lmao.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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