Submission #658829

#	Time	Username	Problem	Language	Result	Execution time	Memory
658829		meiron03	Bank (IZhO14_bank)	C++17	0 / 100	36 ms	82388 KiB

bank

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


typedef pair<int,int> point;
#define Rd(r) freopen(r, "r", stdin);
#define Wt(w) freopen(w, "w", stdout);
#define x first
#define y second
#define INF 1<<30
#define MAXI 20
vector<int> MASK[MAXI];
int dp[MAXI][1 << MAXI];
bool flag = false;
bool DP(int i, int mask) {
  if (i < 0) {
    flag = true;
    return true;
  }
  if (dp[i][mask] > -1) return dp[i][mask];
  int ans = 0;
  for (int state: MASK[i]) {
    if (state & mask) continue;
    ans |= DP(i - 1, mask | state);
    if(flag) return true;
  }
  return dp[i][mask] = ans;
}
 

string ZiwenZapper(int n, int m, int a[], int b[]) {
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) sum += a[i];
        }
        for (int i = 0; i < m; i++) {
            if (sum == b[i]) MASK[i].push_back(mask);
        }
    }
    memset(dp, -1, sizeof(dp));
    DP(n - 1, 0);
end: 
    return (flag) ? "YES" : "NO";

}

int main()
{
    //Rd("ziwenzapper.in");
    //Wt("piepie.out");
    int n, m;
    int a[MAXI], b[MAXI];

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int j = 0; j < m; j++) cin >> b[j];
    string val = ZiwenZapper(n, m, a, b);
    cout << val << endl;
    return 0;

}

Compilation message (stderr)

bank.cpp: In function 'bool DP(int, int)':
bank.cpp:27:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |   return dp[i][mask] = ans;
      |          ~~~~~~~~~~~~^~~~~
bank.cpp: In function 'std::string ZiwenZapper(int, int, int*, int*)':
bank.cpp:43:1: warning: label 'end' defined but not used [-Wunused-label]
   43 | end:
      | ^~~

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