제출 #864036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864036		Mohammadamin__Sh	은행 (IZhO14_bank)	C++17	100 / 100	184 ms	4948 KiB

bank

//In His Name
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1ll,x%y)
const int maxn = 22 , MOD = 1e9 + 7;
const ll INF = 1e18;

int n , m , a[maxn] , c[maxn] , ps[maxn] , dp[(1<<maxn)];

int main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = 0 ; i < m ; i++) cin >> c[i];
    for(int i = 1 ; i <= n ; i++) ps[i] = ps[i-1] + a[i];
    for(int mask = 1 ; mask < (1 << m) ; mask++){
        int maxi = 0 , sum = 0 , cnt = 0 , tmp = mask;
        vector<int> one;
        while(tmp > 0){
            if(tmp & 1) {
                one.pb(cnt);
                sum += c[cnt];
            }
            cnt ++;
            tmp >>= 1;
        }
        for(int i : one) maxi = max(maxi , dp[mask ^ (1<<i)]);
        if(sum == ps[maxi+1])
            dp[mask] = maxi + 1;
        else dp[mask] = maxi;
        if(dp[mask] == n) return cout << "YES" , 0;
    }
    cout << "NO";
}

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