Submission #1274723

#TimeUsernameProblemLanguageResultExecution timeMemory
1274723almazBank (IZhO14_bank)C++20
19 / 100
1 ms584 KiB
#include <bits/stdc++.h> using namespace std; #define int long long // #define endl '\n' #define ff first #define ss second #define pb push_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define ar array const int MOD = 1e9 + 7,INF = 1e18, N = 2e5 + 5; /* 5 2 1 2 2 2 3 2 3 4 2 4 5 2 */ void solve(){ int n, m; cin >> n >> m; vector <int> a(n) , b(m); for(int i = 0;i < n;i++){ cin >> a[i]; } int sum = 0; for(int i = 0;i < m;i++){ cin >> b[i]; sum += b[i]; } vector <int> dp(sum + 1); dp[0] = 1; for(int i = 0;i < m;i++){ for(int j = sum;j >= b[i];j--){ dp[j] += dp[j - b[i]]; } } sort(rall(a)); vector <int> use(m); for(int i = 0;i < n;i++){ if(dp[a[i]] == 0){ cout<<"NO"<<endl; return; } int h = a[i]; for(int j = 0;j < m;j++){ if(h <= 0) break; if(dp[h - b[i]] && !use[i]){ use[i] = 1; h -= b[i]; } } vector <int> dp1(sum + 1); for(int i = 0;i < m;i++){ for(int j = sum;j >= b[i];j--){ if(use[i]) continue; dp1[j] += dp1[j - b[i]]; } } swap(dp1 , dp); } cout<<"YES"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int ti = 1; while (ti--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...