Submission #172672

#	Time	Username	Problem	Language	Result	Execution time	Memory
172672		abacaba	Bank (IZhO14_bank)	C++14	100 / 100	276 ms	5584 KiB

bank

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define y1 abcde
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9;
const int mod = 1e9 + 7;
const int N = 20;
int n, m, a[N], b[N], cur, sum[1 << N];
bool dp[1 << N];

main() {
    scanf("%d %d\n", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf("%d", a + i);
    for(int i = 0; i < m; ++i)
        scanf("%d", b + i);
    for(int mask = 0; mask < (1 << m); ++mask)
        for(int i = 0; i < m; ++i)
            if((1 << i) & mask)
                sum[mask] += b[i];
    dp[0] = true;
    for(int i = 0; i < n; ++i) {
        for(int mask = 0; mask < (1 << m); ++mask) {
            if(sum[mask] < cur || !dp[mask])
                continue;
            int sum_now = sum[mask] - cur;
            for(int j = 0; j < m; ++j)
                if(((1 << j) & mask) == 0)
                    if(sum_now + b[j] <= a[i])
                        dp[mask | (1 << j)] = true;
        }
        cur += a[i];
    }
    for(int mask = 0; mask < (1 << m); ++mask)
        if(sum[mask] == cur && dp[mask])
            return puts("YES"), 0;
    puts("NO");
    return 0;
}

Compilation message (stderr)

bank.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
bank.cpp: In function 'int main()':
bank.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~
bank.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
         ~~~~~^~~~~~~~~~~~~
bank.cpp:53: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