제출 #1277758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277758		alahunovahmad	은행 (IZhO14_bank)	C++20	19 / 100	1 ms	576 KiB

bank

#include<bits/stdc++.h>
//#define int  long long
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	vector<int>a(n),b(m);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	bool ok=true;
	for(int i=0;i<m;i++){
		cin>>b[i];
	}
	sort(a.rbegin(),a.rend());
	sort(b.rbegin(),b.rend());
//	for(auto to:a){
//		cout<<to<<' ';
//	}
//	cout<<"\n";
//	for(auto to:b){
//		cout<<to<<' ';
//	}
//	cout<<"\n";
	
	vector<int>vis(m,-1);
	for(int i=0;i<n;i++){
		vector<bool>dp(a[i]+1,false);
		vector<vector<int>>dp2(a[i]+1);
		
		dp[0]=true;
		dp2[0].push_back(-1);
		for(int j=m-1;j>=0;j--){
			if(b[j]>a[i] || vis[j]==1){
				continue;
			}
			for(int w=a[i]-b[j];w>=0;w--){
				if(dp[w]==true){
					dp[w+b[j]]=true;
					if(!dp2[w].empty()){
					dp2[w+b[j]]=dp2[w];
					dp2[w+b[j]].push_back(j);
				}
				}
			}
//			for(int k=0;k<=a[i];k++){
//				if(dp[k]==true){
//					cout<<"1 ";
//				}else cout<<"0 ";
//			}
		}
		if(dp[a[i]]==true){
				for(int to:dp2[a[i]]){
					if(to==-1) continue;
//					cout<<to<<' ';
					vis[to]=1;
				}
//			cout<<"\n";
		}else{
			ok=false;
			break;
		}
	}
	if(ok==true){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	return 0;
}

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