제출 #710378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710378		JJAnawat	은행 (IZhO14_bank)	C++14	100 / 100	107 ms	8520 KiB

bank

#include<bits/stdc++.h>

#define F first
#define S second

using namespace std;

int n,m;
int a[25],b[25];
pair<int,int> dp[1<<20];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i=1;i<=n;i++)
        cin >> a[i];
    for(int i=0;i<m;i++)
        cin >> b[i];
    for(int i=0;i<(1<<m);i++)
        dp[i]={-1,-1};
    dp[0]={0,0};
    for(int st=1;st<(1<<m);st++){
        for(int j=0;j<m;j++){
            if(st&(1<<j)){
                int prv=st^(1<<j);
                if(dp[prv].F==-1)
                    continue;
                //cout << st << " ";
                int total=dp[prv].S+b[j];
                if(total==a[dp[prv].F+1]){
                    if(dp[prv].F+1>dp[st].F){
                        dp[st]={dp[prv].F+1,0};
                    }
                }
                else{
                    if(dp[prv].F>dp[st].F){
                        dp[st]={dp[prv].F,total};
                    }
                }
            }
        }
        if(dp[st].F==n){
            cout << "YES";
            return 0;
        }
        //cout << dp[st].F << ' ';
    }
    cout << "NO";
}

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