제출 #342040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342040		Kevin_Zhang_TW	Bank (IZhO14_bank)	C++17	0 / 100	46 ms	83052 KiB

bank

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 20, MAX_M = 1001;
int n, m, a[MAX_N], b[MAX_N], sum[1<<MAX_N];
int dp[MAX_N][1<<MAX_N];
vector<int> sumask[MAX_N * MAX_M];
bool dfs(int cur, int mask) {
	if (cur == n) return true;
	if (~dp[cur][mask]) return dp[cur][mask];
	for (int u : sumask[ a[cur] ])
		if ((mask & u) == u && (dp[cur][mask] |= dfs(cur+1, mask ^ u)))
			return true;
	return false;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0;i < n;++i)
		cin >> a[i];
	for (int i = 0;i < m;++i)
		cin >> b[i];

	for (int s = 1;s < 1<<m;++s) {
		sum[s] = b[__lg(s)];
		if (s != s & -s) sum[s] += sum[s ^ (1<<__lg(s))];
		sumask[ sum[s] ].pb(s);
	}

	memset(dp, -1, sizeof(dp));

	puts(dfs(0, (1<<m)-1) ? "YES" : "NO");
}

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'int32_t main()':
bank.cpp:50:9: warning: self-comparison always evaluates to false [-Wtautological-compare]
   50 |   if (s != s & -s) sum[s] += sum[s ^ (1<<__lg(s))];
      |       ~ ^~ ~
bank.cpp:50:9: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   50 |   if (s != s & -s) sum[s] += sum[s ^ (1<<__lg(s))];
      |       ~~^~~~

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