oj.uz

답안 #607623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607623 2022-07-26T21:53:10 Z sushant52 은행 (IZhO14_bank) C++17
52 / 100
 1000 ms 21744 KB 
/////////////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////
#define MOD 1000000009
#define BIG 100000000000000000
#define PB push_back
#define MP make_pair
#define inn(x)   \
	long long x; \
	cin >> x;
#define all(x) (x).begin(), (x).end()
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define spp << " "
#define int long long
const int mod = 5;
int powmod(int a, int b)
{
	int res = 1;
	a %= mod;
	assert(b >= 0);
	for (; b; b >>= 1)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}
// #define endl "\n"

// struct comparator
// {
// 	bool operator()(const pair<int,pair<int,int> > p1 , const pair<int,pair<int,int> > p2)
//  	{
// 		return (p1.first>p2.first || p1.second.first<p2.second.first);
// 	}
// };

// int not_prime[100001]={0};
// int arr[100001]={0};

// void seive()
// {
// 	not_prime[0]=not_prime[1]=1;
// 	for (int i = 2; i * i <= 100000; i++)
// 	{
//     	if(!not_prime[i])
//     	{
//        		for(int j = i * i; j <= 100000; j += i)
//          		not_prime[j] = 1;
//   		}
// 	}
// }

// void kprime()
// {
// 	arr[0]=0;arr[1]=0;arr[2]=1;arr[3]=1;
// 	for(int i=4;i<100001;++i)
// 	{
// 		int temp=i;
// 		for(auto x:prime)
// 		{
// 			if(x*x>temp)
// 				break;
// 			if(temp%x==0)
// 				++arr[i];
// 			while(temp%x==0)
// 				temp/=x;
// 		}
// 		if(temp>1)
// 			++arr[i];
// 	}
// }

int n, m;
vector<int> req;
vector<int> nums;
map<pair<int, int>, bool> dp;

bool recurse(int i, int cur, int mask)
{
	if (i >= req.size())
		return true;
	if (dp.find({cur, mask}) != dp.end())
		return dp[{cur, mask}];
	if (cur == 0)
		return dp[{cur, mask}] = recurse(i + 1, i + 1 < req.size() ? req[i + 1] : 0, mask);
	if (cur < 0)
		return false;

	bool flag = false;

	for (int j = 0; j < m; ++j)
	{
		if (mask & (1 << j))
			flag = flag || recurse(i, cur - nums[j], mask ^ (1 << j));
	}

	return (dp[{cur, mask}] = flag);
}

void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		req.push_back(x);
	}

	for (int i = 0; i < m; ++i)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}

	cout << (recurse(0, req[0], (1 << m) - 1) ? "YES" : "NO");

	return;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// inn(t);
	// while (t--)
	solve();
}

Compilation message

bank.cpp: In function 'bool recurse(long long int, long long int, long long int)':
bank.cpp:85:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  if (i >= req.size())
      |      ~~^~~~~~~~~~~~~
bank.cpp:90:49: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   return dp[{cur, mask}] = recurse(i + 1, i + 1 < req.size() ? req[i + 1] : 0, mask);
      |                                           ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Execution timed out 1097 ms 21744 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 ms 396 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 21 ms 1224 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Execution timed out 1097 ms 21744 KB Time limit exceeded
10 Halted 0 ms 0 KB -