Submission #987787

#	Time	Username	Problem	Language	Result	Execution time	Memory
987787		DalvinT	Bank (IZhO14_bank)	C++17	100 / 100	95 ms	16888 KiB

bank

#include <bits/stdc++.h>
using namespace std;

#define task "task"

#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, b, a) for(int i = b; i >= a; --i)
#define REP(i, n) for(int i = 0; i < n; ++i)

#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define BIT(x, i) ((x) >> (i) & 1)

const ll N = 20;
ll n, m;
ll a[N], b[N];
pll dp[1 << N]; //? {most number of people from left, the money remain}

void solve(int testcase) {
    cin >> n >> m;
    REP(i, n) cin >> a[i];
    REP(i, m) cin >> b[i];
    memset(dp, -1, sizeof dp);
    dp[0] = {0, 0};
    for(ll mask = 0; mask < (1 << m); ++mask) {
        for(ll last = 0; last < m; ++last) {
            if(!BIT(mask, last)) continue;
            ll pre = mask ^ (1 << last);
            if(dp[pre].fi == -1) continue;

            ll newRemain = dp[pre].se + b[last];
            ll need = a[dp[pre].fi];

            if(newRemain < need) {
                dp[mask] = {dp[pre].fi, newRemain};
            } else if(newRemain == need) {
                dp[mask] = {dp[pre].fi + 1, 0};
            }
        }
        if(dp[mask].fi == n) return cout << "YES", void();
    }
    cout << "NO";
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(task == "txtfile") {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    } else if(task != "task") {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    for(ll i = 1; i <= tc; ++i) solve(i);
    return 0;
}

/*EXPLANATION*/

Compilation message (stderr)

bank.cpp: In function 'void solve(int)':
bank.cpp:31:29: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   31 |     memset(dp, -1, sizeof dp);
      |                             ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bank.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
bank.cpp: In function 'int main()':
bank.cpp:57:13: warning: comparison with string literal results in unspecified behavior [-Waddress]
   57 |     if(task == "txtfile") {
      |             ^
bank.cpp:60:20: warning: comparison with string literal results in unspecified behavior [-Waddress]
   60 |     } else if(task != "task") {
      |                    ^
bank.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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