oj.uz

Submission #582474

# Submission time Handle Problem Language Result Execution time Memory
582474 2022-06-23T22:10:20 Z 1ne Bank (IZhO14_bank) C++14
71 / 100
 1000 ms 61900 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<int>arr(n);
	for (int i = 0;i<n;++i)cin>>arr[i];
	vector<int>brr(m);
	for (int i = 0 ;i<m;++i)cin>>brr[i];
	sort(brr.begin(),brr.end());
	vector<vector<int>>pos(n);
	for (int i = 0;i < (1<<m);++i){
		vector<int>cur;
		for (int j = 0;j<m;++j){
			if (i & (1<<j)){
				cur.push_back(brr[j]);
			}
		}
		map<int,int>c;
		c[0] = true;
		for (auto x:cur){
			map<int,int>nex;
			for (auto y:c){
				if (y.first + x <=1000){
					nex[y.first + x] = true;
				}
			}
			swap(nex,c);
		}
		for (int j = 0;j<n;++j){
			if (c[arr[j]]){
				pos[j].push_back(i);
			}
		}
	}
	vector<vector<int>>dp(n,vector<int>((1<<20),-1));
	function<bool(int,int)>solve = [&](int u,int mask){
		if (u == n)return 1;
		if (dp[u][mask]!=-1)return dp[u][mask];
		int ans = 0;
		for (auto x:pos[u]){
			if ((mask & x))continue;
			ans|=solve(u + 1,(mask | x));
		}
		return dp[u][mask] = ans;
	};
	bool ans = solve(0,0);
	if (ans){
		cout<<"YES\n";
	}
	else cout<<"NO\n";
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 5 ms 8532 KB Output is correct
4 Correct 22 ms 8472 KB Output is correct
5 Correct 691 ms 8488 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 5 ms 8468 KB Output is correct
8 Correct 710 ms 8556 KB Output is correct
9 Correct 649 ms 8492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20820 KB Output is correct
2 Correct 9 ms 16640 KB Output is correct
3 Correct 7 ms 12628 KB Output is correct
4 Correct 11 ms 20792 KB Output is correct
5 Correct 18 ms 33148 KB Output is correct
6 Correct 14 ms 24916 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 10 ms 20820 KB Output is correct
9 Correct 11 ms 16724 KB Output is correct
10 Correct 14 ms 24960 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33140 KB Output is correct
2 Correct 16 ms 16704 KB Output is correct
3 Correct 32 ms 45496 KB Output is correct
4 Correct 41 ms 61900 KB Output is correct
5 Correct 36 ms 45428 KB Output is correct
6 Correct 30 ms 24896 KB Output is correct
7 Correct 27 ms 20792 KB Output is correct
8 Correct 23 ms 16696 KB Output is correct
9 Correct 28 ms 37180 KB Output is correct
10 Correct 30 ms 37196 KB Output is correct
11 Correct 36 ms 61828 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 5 ms 8532 KB Output is correct
4 Correct 22 ms 8472 KB Output is correct
5 Correct 691 ms 8488 KB Output is correct
6 Correct 5 ms 8532 KB Output is correct
7 Correct 5 ms 8468 KB Output is correct
8 Correct 710 ms 8556 KB Output is correct
9 Correct 649 ms 8492 KB Output is correct
10 Correct 10 ms 20820 KB Output is correct
11 Correct 9 ms 16640 KB Output is correct
12 Correct 7 ms 12628 KB Output is correct
13 Correct 11 ms 20792 KB Output is correct
14 Correct 18 ms 33148 KB Output is correct
15 Correct 14 ms 24916 KB Output is correct
16 Correct 9 ms 16724 KB Output is correct
17 Correct 10 ms 20820 KB Output is correct
18 Correct 11 ms 16724 KB Output is correct
19 Correct 14 ms 24960 KB Output is correct
20 Correct 27 ms 33140 KB Output is correct
21 Correct 16 ms 16704 KB Output is correct
22 Correct 32 ms 45496 KB Output is correct
23 Correct 41 ms 61900 KB Output is correct
24 Correct 36 ms 45428 KB Output is correct
25 Correct 30 ms 24896 KB Output is correct
26 Correct 27 ms 20792 KB Output is correct
27 Correct 23 ms 16696 KB Output is correct
28 Correct 28 ms 37180 KB Output is correct
29 Correct 30 ms 37196 KB Output is correct
30 Correct 36 ms 61828 KB Output is correct
31 Correct 773 ms 12732 KB Output is correct
32 Correct 879 ms 16840 KB Output is correct
33 Correct 882 ms 33072 KB Output is correct
34 Correct 859 ms 45484 KB Output is correct
35 Correct 891 ms 49580 KB Output is correct
36 Execution timed out 1068 ms 212 KB Time limit exceeded
37 Halted 0 ms 0 KB -