Submission #545677

#	Time	Username	Problem	Language	Result	Execution time	Memory
545677		AA_Surely	Bank (IZhO14_bank)	C++17	100 / 100	128 ms	8608 KiB

bank

#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 22;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, m, ns[2][MAXN];
int ps[MAXN], sum[1 << MAXN];
int dp[1 << MAXN];

int main() {
    IOS;
    
    cin >> n >> m;
    FOR(i, 1, n + 1) {
        cin >> ns[0][i];
        ps[i] = ps[i - 1] + ns[0][i];
    }

    F0R(i, m) cin >> ns[1][i];

    FOR(mask, 1, (1 << m)) F0R(b, m) if ((mask >> b) & 1)
        sum[mask] += ns[1][b];
    
    FOR(mask, 1, (1 << m)) {
        F0R(b, m) if ((mask >> b) & 1) dp[mask] = max(dp[mask], dp[mask ^ (1 << b)]);
        if (!binary_search(ps, ps + n + 1, sum[mask])) continue;
        int place = lower_bound(ps, ps + n + 1, sum[mask]) - ps;
        if (dp[mask] == place - 1) dp[mask]++;
    }

    cout << (dp[(1 << m) - 1] == n ? "YES" : "NO");
}

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