제출 #841572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841572		hqminhuwu	은행 (IZhO14_bank)	C++14	100 / 100	161 ms	5676 KiB

bank

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

string w[2] = {"NO","YES"};
int n,m,a[N],i,dp[(1 << 21)],b[N],j;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    forr (i,1,n)
        cin >> a[i],a[i] += a[i - 1];
    a[n + 1] = oo;
    forr (i,0,m - 1)
        cin >> b[i];
    dp[0] = 1;
    forr (i,1,(1 << m) - 1){
        int sum = 0;
        forr (j,0,m - 1)
        if ((1 << j) & i)
            sum += b[j];
        int k = 0;
        while (a[k] < sum)
            k++;
        forr (j,0,m - 1)
            if ((1 << j) & i)
                dp[i] |= dp[i ^ (1 << j)] && (sum - b[j] >= a[k - 1]);
        if (sum == a[n] && dp[i]){
            cout << "YES\n";
            return 0;
        }
      if (i == (1 << m) - 1 && sum < a[n]){
        cout << "NO\n";
        return 0;
      }
    }
    cout << w[dp[(1 << m) - 1]];
    return 0;
}
/*



*/

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