Submission #580474

#	Time	Username	Problem	Language	Result	Execution time	Memory
580474		FatihSolak	Bank (IZhO14_bank)	C++17	71 / 100	1083 ms	1540 KiB

bank

#include <bits/stdc++.h>
#define N 20
using namespace std;
int a[N];
int b[N];
bool ok[(1<<N)];
void solve(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    for(int i = 0;i<m;i++){
        cin >> b[i];
    }
    while(n && m){
        bool ok = 0;
        for(int i = 0;i<n && !ok;i++){
            for(int j = 0;j<m && !ok;j++){
                if(a[i] == b[j]){
                    ok = 1;
                    n--,m--;
                    for(int c = i;c<n;c++){
                        a[c] = a[c+1];
                    }
                    for(int c = j;c<m;c++){
                        b[c] = b[c+1];
                    }
                }
            }
        }
        if(!ok)break;
    }
    if(n*2 > m){
        cout << "NO" << endl;
        return;
    }
    vector<int> masks = {0};
    for(int i = 0;i<n;i++){
        vector<int> nw;
        for(auto u:masks){
            vector<int> unused;
            for(int j = 0;j<m;j++){
                if( !(u & (1<<j)))
                    unused.push_back(j);
            }
            for(int mask = 0;mask<(1<<unused.size());mask++){
                int nwmask = u;
                int tot = 0;
                for(int j = 0;j<unused.size();j++){
                    if(mask & (1<<j)){
                        tot += b[unused[j]];
                        nwmask |= (1<<unused[j]);
                    }
                }
                if(tot == a[i])
                    nw.push_back(nwmask);
            }
        }
        sort(nw.begin(),nw.end());
        nw.resize(unique(nw.begin(),nw.end())-nw.begin());
        swap(masks,nw);
    }
    if(masks.empty()){
        cout << "NO" << endl;
    }
    else cout << "YES" << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Compilation message (stderr)

bank.cpp: In function 'void solve()':
bank.cpp:50:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 for(int j = 0;j<unused.size();j++){
      |                               ~^~~~~~~~~~~~~~

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