Submission #171390

#	Time	Username	Problem	Language	Result	Execution time	Memory
171390		Swan	Bank (IZhO14_bank)	C++14	100 / 100	540 ms	2668 KiB

bank

#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;

const int maxn = 20;

vector<int> a,b;
vector<int> masks[22];

map<int,vector<int> > qwe;
bitset<(1<<20)> dp[20];

main(){
    ios_base::sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        b.push_back(x);
        qwe[x].push_back(i);
    }
    for(int i(0); i < m;i++){
        int x; cin >> x;
        a.push_back(x);
    }
    for(int i(0); i < (1<<m);i++){
        int sum = 0;
        for(int j(0); j < m;j++){
            int bit = i&(1<<j);
            if(!bit)continue;
            else sum+=a[j];
        }
        //cout << sum << endl;
        if(!qwe.count(sum))continue;
        //cout << sum << endl;
        for(int j(0); j < qwe[sum].size();j++){
            //cerr << qwe[j][i] << endl;
            if(!qwe[sum][j]){
                dp[0][i] = 1;
                //cout << sum << endl;
            }
            masks[qwe[sum][j]].push_back(i);
            //cout << qwe[j][i] << ' ' << i << endl;
        }
    }
    for(int k(0); k < n-1;k++){
        for(int mask(0); mask < (1<<m);mask++){
            if(!dp[k][mask])continue;
            for(int z(0); z < masks[k+1].size();z++){
                int to = masks[k+1][z];
                bool f = (mask&to);
                if(f)continue;
                dp[k+1][to^mask] = 1;
                //cout << k+1 << ' ' << mask << ' ' << to << ' ' << (to^mask) << endl;
            }
        }
    }
    for(int mask(0); mask < (1<<m);mask++){
        if(dp[n-1][mask]){
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}
/*
1 5
8
4 2 5 1 3

*/

Compilation message (stderr)

bank.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bank.cpp: In function 'int main()':
bank.cpp:40:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0); j < qwe[sum].size();j++){
                       ~~^~~~~~~~~~~~~~~~~
bank.cpp:53:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int z(0); z < masks[k+1].size();z++){
                           ~~^~~~~~~~~~~~~~~~~~~

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