제출 #167736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167736		achibasadzishvili	은행 (IZhO14_bank)	C++14	100 / 100	176 ms	12792 KiB

bank

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,m,a[205],b[205];
ll sum[3000005],ind[3000005],dp[3000005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }
    a[n + 1] = a[n];
    for(int i=1; i<=m; i++){
        cin >> b[i];
    }
    sum[0] = 0;
    
    for(int i=1; i<=m; i++)
        for(int j=0; j<(1 << m); j++)
            if((j & (1 << (i - 1))) == 0)
                sum[j | (1 << (i - 1))] = sum[j] + b[i];
    
    dp[0] = 1;
    
    for(int j=0; j<(1 << m); j++){
        ll lst = 0;
        for(int i=1; i<=n; i++)
            if(a[i] <= sum[j])
                lst = i;
        ind[j] = lst;
    }
    for(int j=1; j<(1 << m); j++)
        for(int i=1; i<=m; i++)
            if(j & (1 << (i - 1)))
                if(sum[j] <= a[ind[j - (1 << (i - 1))] + 1] && dp[j - (1 << (i - 1))])
                    dp[j] = 1;
    
    for(int i=0; i<(1 << m); i++)
        if(ind[i] == n && dp[i]){
            cout << "YES";
            return 0;
        }
    
    cout << "NO";
    
    return 0;
}

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