Submission #495502

#	Time	Username	Problem	Language	Result	Execution time	Memory
495502		adhitya	Bank (IZhO14_bank)	C++14	100 / 100	125 ms	4396 KiB

bank

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int n,m;
vector<int> salary,coin;
int solve(int mask,int index,int curwt,vector<int>& dp){
    if(index==n)   return 1;
    if(dp[mask]!=-1)    return dp[mask];
    dp[mask] = 0;
    for(int i=0;i<m;i++){
        if((mask & (1<<i)) == 0){
            // ith coin can be used
            if(salary[index] > curwt + coin[i]){
                dp[mask] = max(dp[mask],solve(mask|(1<<i),index,curwt+coin[i],dp));
                if(dp[mask]==1)    break;
            }else if(salary[index]==curwt+coin[i]){
                dp[mask] = max(dp[mask], solve(mask|(1<<i),index+1,curwt+coin[i],dp));
                if(dp[mask]==1)    break;
            }
        }
    }
    return dp[mask];
    
}
int main(){
    cin >> n >> m;
    salary.resize(n);
    for(int i=0;i<n;i++){
        cin >> salary[i];
    }
    coin.resize(m);
    for(int i=0;i<m;i++){
        cin >> coin[i];
    }
    for(int i=1;i<n;i++){
        salary[i] += salary[i-1];
    }
    vector<int> dp(1<<m,-1);
    solve(0,0,0,dp);
    // dp[mask] => whether we can pay remaining person with unset bits of coins where remaining person is specified by the sum of used coins
    if(dp[0])   cout<<"YES\n";
    else    cout<<"NO\n";
    
    return 0;
}

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