제출 #1105543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105543		Newtonabc	은행 (IZhO14_bank)	C++14	100 / 100	171 ms	82512 KiB

bank

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
int dp[21][N],p[30],b[30];
int main(){
    int n,m;
    cin>>n >>m;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<m;i++) cin>>b[i];
    int lp=1<<m;
    for(int i=0;i<n;i++) for(int j=0;j<lp;j++) dp[i][j]=INT_MAX;
    dp[0][0]=p[0];
    for(int i=0;i<n;i++) for(int j=0;j<lp;j++){
        if(dp[i][j]==INT_MAX) continue;
        for(int k=0;k<m;k++){
            if(j&(1<<k)) continue;
            if(dp[i][j]-b[k]>=0) dp[i][j|(1<<k)]=dp[i][j]-b[k];
            if(dp[i][j|(1<<k)]==0){
                if(i==n-1){
                    cout<<"YES";
                    return 0;
                }
                dp[i+1][j|(1<<k)]=min(dp[i+1][j|(1<<k)],p[i+1]);
            }
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<lp;j++){
            cout<<dp[i][j] <<" ";
        }
        cout<<"\n";
    }*/
    cout<<"NO";
}

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