Submission #696087

#	Time	Username	Problem	Language	Result	Execution time	Memory
696087		aedmhsn	Bank (IZhO14_bank)	C++17	100 / 100	133 ms	8496 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(); cout.tie()
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;

const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

const int mxN=20;

pii dp[(1 << mxN)];



int main(){
    int n, m;
    cin >> n >> m;
    vector <int> v(n);
    vector <int> coins(m);
    for(int i=0; i<n; i++) cin >> v[i];
    for(int i=0; i<m; i++) cin >> coins[i];
    bool valid=false;
    for(int i=0; i<(1 << m); i++){
        for(int j=0; j<m; j++){
            if((i & (1 << j))) continue;
            int nmsk = (i | (1 << j));
            if(dp[i].B + coins[j] == v[dp[i].A]){
                dp[nmsk] = max(dp[nmsk], {dp[i].A+1, 0});
            }
            else if(dp[i].B + coins[j] < v[dp[i].A]){
                dp[nmsk] = max(dp[nmsk], {dp[i].A, dp[i].B+coins[j]});
            }
            if(dp[nmsk].A == n){
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:37:10: warning: unused variable 'valid' [-Wunused-variable]
   37 |     bool valid=false;
      |          ^~~~~

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