oj.uz

Submission #738467

# Submission time Handle Problem Language Result Execution time Memory
738467 2023-05-08T19:57:56 Z MODDI Bank (IZhO14_bank) C++14
19 / 100
 91 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vi banknotes, salary;
bool check_bit(int n, int bit){
	int ok = n & (1 << bit);
	if(ok)	return true;
	return false;
}
int set_bit(int n, int b){
	return (n | (1 << b));
}
bool can[21][1001];
bool dp[21][1001][(1<<14)];
bool f(int at, int sum, int mask){
	if(sum > salary[at])	return false;
	if(at >= n)	return true;
	if(dp[at][sum][mask])	return true;
	if(sum == salary[at]){
		bool ans = f(at+1, 0, mask);
		return dp[at][sum][mask] = ans;
	}
	else{
		bool ans = false;
		for(int i = 0; i < m; i++){
			if(!check_bit(mask, i)){
				int new_mask = set_bit(mask, i);
				ans |= f(at, sum + banknotes[i], new_mask);
			}
		}
		return dp[at][sum][mask] = ans;
	}
}
int main(){
	cin>>n>>m;
	banknotes.resize(m);
	salary.resize(n);
	for(int i = 0; i < n; i++)	cin>>salary[i];
	for(int i = 0; i < m; i++)	cin>>banknotes[i];
	sort(salary.begin(), salary.end());
	if(n == 1){
		memset(can, false, sizeof can);
		can[0][0] = can[0][banknotes[0]] = true;
		for(int i = 1; i < m; i++){
			for(int j = 0; j <= 1000; j++){
				can[i][j] |= can[i-1][j];
				if(j >= banknotes[i])
					can[i][j] |= can[i-1][j-banknotes[i]];
			}
		}
		if(can[m-1][salary[0]])	cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	else if(m <= 14){
		memset(dp, false, sizeof dp);
		bool ans = f(0, 0, 0);
		if(ans)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	else
		cout<<"NO"<<endl; //TODO
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Runtime error 90 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -