Submission #1001953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001953		idkman	Bank (IZhO14_bank)	C++17	100 / 100	89 ms	16988 KiB

bank

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll  i=(a);i<=(b);i++)
#define Ford(i,a,b) for(ll  i=(a);i>=(b);i--)
#define inf 1000000000000000000
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define endl "\n"
using namespace std;
int Dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
int Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
const ll N = 100000;
const int block_size = 300;
const int MOD = 1e9 + 7; /* 998244353 */
const int LOG = 31;
const int K = 20;
ll nph(ll k, ll x) { return ((x >> k) & 1); }
ll n,m,a[25],b[25];
pair<ll, ll> dp[1<<20];
void Solve() {
	cin>>n>>m;
	For(i, 1, n) cin>>a[i];
	For(i, 0, m-1) cin>>b[i];
	For(i, 0, (1 << m) - 1) dp[i] = {-inf, -inf};
	dp[0] = {0, 0};
	for(ll mask = 1; mask < (1 << m); mask++) {
		for(ll last = 0; last < m; last++) {
			if(nph(last, mask)) {
				ll oldmask = mask ^ (1 << last);
				if(dp[oldmask].fi == -inf) continue;
				ll need = a[dp[oldmask].fi + 1];
				ll have = dp[oldmask].se + b[last];
				if(have == need) {
					dp[mask].fi = max(dp[mask].fi, dp[oldmask].fi + 1);
					dp[mask].se = 0;
				}
				else {
					if(have < need) {
						dp[mask].se = have;
						dp[mask].fi = dp[oldmask].fi;
					}
				}
				
			}
		}
		if(dp[mask].fi == n) {cout << "YES"; return;}
	}
	cout << "NO";
}

int main() {
    // freopen("SUMMAX.inp", "r", stdin);
    // freopen("SUMMAX.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--) {
        Solve();
    }
}

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