oj.uz

Submission #968141

# Submission time Handle Problem Language Result Execution time Memory
968141 2024-04-23T07:56:51 Z UmairAhmadMirza Bank (IZhO14_bank) C++17
46 / 100
 79 ms 10860 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=21;
int const mod=1e9+7;

int sal[N];
int coin[N];
int prefix_done[1<<N];
int leftover[1<<N];
int main(){
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < n; ++i)
		cin>>sal[i];
	for (int i = 0; i < m; ++i)
		cin>>coin[i];
	for (int i = 0; i < (1<<m); ++i){
		prefix_done[i]=-1;
		leftover[i]=-1;
	}
	leftover[0]=0;
	prefix_done[0]=0;
	for(int mask=0;mask<(1<<m);mask++){
		for(int c=0;c<m;c++){
			if(((1<<c)&mask)==0)
				continue;
			int mk=mask-(1<<c);
			int lft=leftover[mk]+coin[c];
			int man_tar=prefix_done[mk];
			if(sal[man_tar]==lft){
				prefix_done[mask]=man_tar+1;
				leftover[mask]=0;
			}
			else if(sal[man_tar]>lft){
				prefix_done[mask]=man_tar;
				leftover[mask]=lft;
			}
		}
		// cout<<mask<<' '<<prefix_done[mask]<<' '<<leftover[mask]<<endl;
		if(prefix_done[mask]==n){
			// cout<<mask<<endl;
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 79 ms 10856 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 10680 KB Output is correct
9 Correct 71 ms 10860 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Incorrect 1 ms 2492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2556 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2456 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 79 ms 10856 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 10680 KB Output is correct
9 Correct 71 ms 10860 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2496 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Incorrect 1 ms 2492 KB Output isn't correct
17 Halted 0 ms 0 KB -