Submission #1344915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344915		aladdin1	Bank (IZhO14_bank)	C++20	100 / 100	109 ms	4532 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 25;
int a[N],b[N],dp[N];
int main(){
    int n,m;cin>>n>>m;
    for (int i=0;i<n;i++) {
        cin>>a[i];
        if(i>0)a[i]+=a[i-1];
    }
    for (int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int mask=0;mask<(1<<m);mask++){
        if(dp[mask]==n)break;
        int sum=a[dp[mask]];
        for(int i=0;i<m;i++){
            if(mask&(1<<i)){
                sum-=b[i];
            }
        }
        for(int i=0;i<m;i++){
            if(mask&(1<<i))continue;
            dp[mask|(1<<i)]=max(dp[mask|(1<<i)],dp[mask]+(sum==b[i]));
        }
    }
    for(int i=0;i<(1<<m);i++){
        if(dp[i]==n){
            cout<<"YES";
            return 0;
        }

    }
    cout<<"NO";
}

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