Submission #172430

#	Time	Username	Problem	Language	Result	Execution time	Memory
172430		abacaba	Bank (IZhO14_bank)	C++14	71 / 100	1012 ms	20984 KiB

bank

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#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], tot;
int sum[1 << N];
bool dp[N + 1][1 << N];

main() {
    scanf("%d %d", &n, &m);
    tot = (1 << m) - 1;
    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];
    for(int i = 0; i < n; ++i) {
        for(int mask = 0; mask < (1 << m); ++mask) {
            if(sum[mask] != a[i])
                continue;
            for(int cur_mask = tot ^ mask; ; cur_mask = ((cur_mask - 1) & (tot ^ mask))) {
                if(i == 0 || dp[i-1][cur_mask])
                    dp[i][mask | cur_mask] = true;
                if(cur_mask == 0)
                    break;
            }
        }
    }
    for(int mask = 0; mask < (1 << m); ++mask)
        if(dp[n-1][mask])
            return puts("YES"), 0;
    puts("NO");
    return 0;
}

Compilation message (stderr)

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