제출 #1016514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016514		soumil69	은행 (IZhO14_bank)	C++17	100 / 100	451 ms	74524 KiB

bank

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

#define ve vector
#define ll long long

ll mod=1e9+7ll;
ll exp(ll n,ll po){
    ll ans=1;
    while(po){
        if(po&1ll){
            ans*=n;
            ans%=mod;
        }
        n*=n;
        n%=mod;
        po>>=1;
    }
    return ans;
}
string bin(int a,int k){
    string s="";
    for(int i=k-1;i>-1;i--){
        if(a&(1<<i)){
            s+='1';
        }
        else{
            s+='0';
        }
    }
    return s;
}
void yay(bool a){
    if(a){
        cout<<"YES";
    }
    else{
        cout<<"NO";
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    ve<int> ppl (n),money(m);
    ve<int> sums(n+1,0);
    for(int i=0;i<n;i++){
        cin>>ppl[i];
        sums[i+1]=sums[i]+ppl[i];
    }
    for(int i=0;i<m;i++){
        cin>>money[i];
    }
    int tot=(1<<m);
    ve<ve<bool> > can(tot,ve<bool> (n+1,0));
    can[0][0]=1;
    for(int msk=1;msk<tot;msk++){
        can[msk][0]=1;
        int sm=0;
        for(int j=0;j<m;j++){
            if(msk&(1<<j)){
                sm+=money[j];
            }
        }
        int l=-1;
        for(int i=0;i<=n;i++){
            if(sums[i]==sm){
                l=i;
                break;
            }
        }
        if(l!=-1 && can[msk][l-1]){
            can[msk][l]=1;
        }
        for(int j=0;j<m;j++){
            if(msk&(1<<j)){
                continue;
            }
            int nex=msk^(1<<j);
            for(int i=1;i<=n;i++){
                if(can[msk][i]){
                    can[nex][i]=1;
                }
            }
        }
    }
    yay(can[tot-1][n]);
}

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