제출 #1232082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232082		warrenn	은행 (IZhO14_bank)	C++20	100 / 100	109 ms	16824 KiB

bank

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

signed main(){
    int n,m;
    cin>>n>>m;
    int a[n+1];
    for(int q=1;q<=n;q++){
        cin>>a[q];
    }
    int b[m+1];
    for(int q=0;q<m;q++){
        cin>>b[q];
    }

    int dp[(1<<m)][2];
    memset(dp,-1,sizeof dp);
    dp[0][0]=1;
    dp[0][1]=0;

    bool oke=false;
   
    for(int q=1;q<(1<<m);q++){
        for(int w=0;w<m;w++){
            if((q>>w)&1){
                int prev=(q ^ (1<<w));
                if(dp[prev][0]==-1)continue;
                int bayar=a[dp[prev][0]];
                int uang=dp[prev][1]+b[w];

                if(bayar==uang){
                    dp[q][0]=dp[prev][0]+1;
                    dp[q][1]=0;
                }
                else if(bayar>uang){
                    dp[q][0]=dp[prev][0];
                    dp[q][1]=uang;
                }
            }
        }
        if(dp[q][0]==n+1){
            oke=true;
        }
       // cout<<dp[q][0]<<" "<<q<<endl;
    }
    if(oke){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

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