Submission #1045149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045149		ivopav	Bank (IZhO14_bank)	C++17	100 / 100	81 ms	7308 KiB

bank

#include <bits/stdc++.h>
using namespace std;

void precomp(int ind,vector<int>& lis,int sad,vector<int>& rje,int zbr){
    //cout << ind << "\n";
    rje[sad]=zbr;
    if (ind>=lis.size()){
        return;
    }
    precomp(ind+1,lis,sad,rje,zbr);
    precomp(ind+1,lis,sad+(1<<ind),rje,zbr+lis[ind]);
    
}

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<int> lis={};
    vector<int> pref={0};
    for (int i=0;i<n;i++){
        int unos;
        cin >> unos;
        lis.push_back(unos);
        pref.push_back(pref.back()+unos);
    }
    vector<int> lis2={};
    for (int i=0;i<m;i++){
        int unos;
        cin >> unos;
        lis2.push_back(unos);
    }
    vector<vector<bool>> dp(n+1,vector<bool>(1<<m,0));
    dp[0][0]=1;
    vector<int> rje(1<<m,0);
    precomp(0,lis2,0,rje,0);
    //for (int i=0;i<(1<<m);i++){
    //    cout << rje[i] << "\n";
    //}
    bool dob=0;
    for (int i=0;i<n;i++){
        for(int j=0;j<(1<<m);j++){
            if (dp[i][j]==0){
                continue;
            }
          //  cout << i << " " << j << "\n";
            int zadval=pref[i+1];
            zadval-=rje[j];
         //   cout << zadval << "\n";
            for (int k=0;k<m;k++){
              //  cout << k << " " << (j|(1<<k)) << "\n";
                if ((j&(1<<k))==0 && zadval>lis2[k]){
                    dp[i][j|(1<<k)]=1;
                }
                if ((j&(1<<k))==0 && zadval==lis2[k]){
                    dp[i+1][j|(1<<k)]=1;
                    if (i==n-1){
                        dob=true;
                    }
                }
                
            }
        }
    }
    if (dob){
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }

}

Compilation message (stderr)

bank.cpp: In function 'void precomp(int, std::vector<int>&, int, std::vector<int>&, int)':
bank.cpp:7:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     if (ind>=lis.size()){
      |         ~~~^~~~~~~~~~~~

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