Submission #1002163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002163		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	78 ms	17696 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define bw(i, a, b) for (auto i = a; i >= b; i--)
#define fw(i, a, b) for (auto i = a; i <= b; i++)
//Road to Expert: 180 pts left
void solve() {
    int n, m; scanf("%d %d", &n, &m);
    int a[n], b[m];
    fw(i, 0, n - 1) scanf("%d", &a[i]);
    fw(i, 0, m - 1) scanf("%d", &b[i]);
    std::pair<int, int> dp[(1 << m)];
    int vis[(1 << m)];//used bit
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;
    dp[0] = {0, 0};
    std::vector<std::vector<int>> masks(30);
    fw(i, 0, (1 << m) - 1) masks[__builtin_popcount(i)].push_back(i);
    fw(i, 0, m) {
        for (auto mask : masks[i]) {
            if (vis[mask]) {
                if (dp[mask].first == n) {
                    printf("YES");
                    return;
                }
                int cp = dp[mask].first;
                fw(j, 0, m - 1) {
                    int mask2 = mask | (1 << j);
                    if (mask - mask2) {
                        if (dp[mask].second + b[j] > a[cp]) continue;
                        vis[mask2] = 1;
                        dp[mask2] = {cp, dp[mask].second + b[j]};
                        if (a[cp] == dp[mask].second + b[j]) dp[mask2] = {cp + 1, 0};
                    }
                }
            }
        }
    }

    printf("NO");
}

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);

    int T_ = 1;
    // scanf("%d", &T_);
    while (T_--) solve();

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'void solve()':
bank.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:10:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     fw(i, 0, n - 1) scanf("%d", &a[i]);
      |                     ~~~~~^~~~~~~~~~~~~
bank.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     fw(i, 0, m - 1) scanf("%d", &b[i]);
      |                     ~~~~~^~~~~~~~~~~~~

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