Submission #16939

#	Time	Username	Problem	Language	Result	Execution time	Memory
16939		erdemkiraz	Bank (IZhO14_bank)	C++98	100 / 100	121 ms	4756 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 20;
const int MAX = 1 << 20;

int n, m;
int a[N], b[N], dp[MAX];

int f(int mask, int x, int sum) {
    if(x == n)
        return 1;
    int &r = dp[mask];
    if(r != -1)
        return r;
    r = 0;
    for(int i = 0; i < m; i++) {
        if(!(mask & 1 << i) and sum + b[i] <= a[x]) {
            if(sum + b[i] == a[x])
                r |= f(mask | 1 << i, x + 1, 0);
            else
                r |= f(mask | 1 << i, x, sum + b[i]);
        }
    }
    return r;
}

int main() {

    scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++)
        scanf("%d", a + i);

    for(int i = 0; i < m; i++)
        scanf("%d", b + i);

    memset(dp, -1, sizeof(dp));

    if(f(0, 0, 0))
        puts("YES");
    else
        puts("NO");

    return 0;

}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
         ~~~~~^~~~~~~~~~~~~
bank.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", b + i);
         ~~~~~^~~~~~~~~~~~~

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