제출 #1326562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326562		ayxanesedzade10	은행 (IZhO14_bank)	C++20	100 / 100	164 ms	16808 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define ld long double
using namespace std;
int main()
{
    ll n,m;cin>>n>>m;
    ll a[n+5],b[m+5],pre[n+5];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    ll dp[(1<<m)+5],ind1[(1<<m)+5];
    pre[0]=a[0];
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=0;i<(1<<m)+5;i++){dp[i]=0;ind1[i]=0;}
    dp[0]=1;
    for(int mask=1;mask<(1<<m);mask++){
        ll sum=0,ind=0,s1=0;
        for(int j=0;j<m;j++){
            if(mask&(1<<j)) sum+=b[j];
        }
        for(int i=0;i<n;i++){
            if(sum>=pre[i]) ind++;
        }
        ind1[mask]=ind;
        for(int j=0;j<m;j++){
            if(mask&(1<<j)){
                ll c=mask-(1<<j);
                if(dp[c] and sum<=pre[ind1[c]]){
                    dp[mask]=1;
                }
            }
        }
        if(dp[mask] and sum==pre[n-1]){
            cout<<"YES"<<endl;return 0;
        }
    }
    cout<<"NO"<<endl;
}

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