Submission #332221

#	Time	Username	Problem	Language	Result	Execution time	Memory
332221		topovik	Bank (IZhO14_bank)	C++14	0 / 100	149 ms	262148 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define f first
#define s second
#define pb push_back
#define INF 1000000000

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<
ll,
null_type,
greater<ll>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

const ll N = 1 << 20;
const int M = 21;

int dp[N][M], dp1[N][M];
set <int> st[N][M];

int gd[N];

int main()
{
    freopen("bank.in", "r", stdin);
    freopen("bank.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    int a[n], b[m];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    swap(n, m);
    for (int i = 0; i < (1 << n); i++)
    {
        int kol = 0;
        for (int j = 0; j < n; j++) kol += (a[i]&(1 << j)) > 0;
        gd[i] = kol;
    }
    st[0][0].insert(0);
    for (int j = 0; j < m; j++)
    {
        for (int i = 0; i < (1 << n); i++)
          if ((n - gd[i]) >= (m - j))
        {
            if (st[i][j].find(a[j]) != st[i][j].end()) dp[i][j] = 1;
            if (dp[i][j] > 0)
            {
                st[i][j + 1].insert(0);
                continue;
            }
            for (auto g : st[i][j])
            {
                for (int c = 0; c < n; c++)
                    if (!((1 << c)&i) && g + b[c] <= a[j] && (n - gd[i + (1 << c)]) >= (m - j)) st[i + (1 << c)][j].insert(g + b[c]);
            }
        }
    }
    for (int i = 0; i <= (1 << n); i++)
        if (st[i][m].find(0) != st[i][m].end()) {cout << "YES";return 0;}
    cout << "NO";
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     freopen("bank.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     freopen("bank.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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