제출 #656381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656381		boykut	은행 (IZhO14_bank)	C++14	71 / 100	1087 ms	11364 KiB

bank

#include <iostream>
#include <vector>

using namespace std;

const int N = 22;
int a[N], b[N], dp[N][1<<N], n, m;
vector<int> can[1001];

int Sum(int mask) {
	int s = 0;
	for (int i = 0; i < m; i++) {
		if ((mask>>i)%2 == 1) s += b[i];
	}
	return s;
}

int main() {
	cin.tie()->sync_with_stdio(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 mask = 0; mask < (1<<m); mask++) {
		int s = Sum(mask);
		if (s <= 1000)
			can[s].push_back(mask);
	}
	
	for (int i = 0; i < can[a[0]].size(); i++)
		dp[0][can[a[0]][i]] = 1;
		
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1<<m); mask++) {
			if (Sum(mask) < a[i]) continue;
			for (int j = 0; j < can[a[i]].size(); j++) {
				int p = can[a[i]][j];
				if ((mask & p) == p) {
					if (dp[i - 1][mask ^ p] == 1)
						dp[i][mask] = 1;
				}
			}
		}
	}
	for (int mask = 0; mask < (1<<m); mask++) {
		if (dp[n-1][mask] == 1)
			return cout << "YES", 0;
	}
	return cout << "NO", 0;
}

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

bank.cpp: In function 'int main()':
bank.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < can[a[0]].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
bank.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int j = 0; j < can[a[i]].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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