제출 #495562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495562		maomao90	은행 (IZhO14_bank)	C++17	100 / 100	876 ms	42180 KiB

bank

// I will instruct you and teach you in the way you should go;
// I will counsel you with my loving eye on you. Psalms 32:8
#include <bits/stdc++.h> 
using namespace std;

#pragma GCC optimize("unroll-loops")

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 20
#define MAXNP 1100000

int n, m;
int a[MAXN], b[MAXN];
int dp[MAXNP], pdp[MAXNP];
vi mp[MAXNP];

int main() {
	int _t = 1;
   	// scanf("%d", &_t);
	while (_t--) {
		scanf("%d%d", &n, &m);
		REP (i, 0, n) {
			scanf("%d", &a[i]);
		}
		REP (i, 0, m) {
			scanf("%d", &b[i]);
		}
		REP (j, 0, 1 << m) {
			REP (i, 0, m) {
				if (j >> i & 1) {
					pdp[j] += b[i];
				}
			}
			mp[pdp[j]].pb(j);
		}
		int sm = 0;
		REP (i, 0, n) {
			sm += a[i];
			REP (j, 0, 1 << m) {
				dp[j] = INF;
			}
			for (int j : mp[sm]) {
				if (pdp[j] == a[i]) {
					dp[j] = 0;
				}
			}
			REP (j, 0, 1 << m) {
				if (dp[j] == 0) continue;
				int x = j;
				while (x) {
					int k = 31 - __builtin_clz(x & -x);
					if (dp[j ^ (1 << k)] != INF) {
						dp[j] = dp[j ^ (1 << k)] + b[k];
						break;
					}
					x -= 1 << k;
				}
			}
			swap(dp, pdp);
		}
		if (pdp[(1 << m) - 1] != INF) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}

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

bank.cpp: In function 'int main()':
bank.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
bank.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |    scanf("%d", &a[i]);
      |    ~~~~~^~~~~~~~~~~~~
bank.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    scanf("%d", &b[i]);
      |    ~~~~~^~~~~~~~~~~~~

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