제출 #1197047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197047		timeflew	은행 (IZhO14_bank)	C++20	100 / 100	117 ms	8620 KiB

bank

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

#define ll long long
#define ff first
#define ss second

pair<int, int> dp[1<<20];//idx sum
int a[21], b[21], pre[21];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<m; i++) cin>>b[i];
    for(int i=0; i<(1<<m); i++) {
        dp[i]={0, 0};
        for(int j=0; j<m; j++) {
            if(i>>j&1) {
                int idx=dp[i^1<<j].ff, s=dp[i^1<<j].ss; 
                if(b[j]+s==a[idx]) {
                    idx++;
                    s=0;
                } else if(b[j]+s<a[idx]) {
                    s+=b[j];
                }
                if(idx==n) {
                    cout<<"YES";
                    return 0;
                }
                dp[i]=max(dp[i], {idx, s});
            }
        }
    }
    cout<<"NO";
    return 0;
}

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