Submission #755184

#TimeUsernameProblemLanguageResultExecution timeMemory
755184vjudge1Bank (IZhO14_bank)C++17
100 / 100
184 ms33240 KiB
#include <bits/stdc++.h> using namespace std; long long dp[(1<<21)]; long long a[21]; long long b[21]; long long tong[(1<<21)]; long long vt[(1<<21)]; long long thua[(1<<21)]; signed main () { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,m; cin >> n >> m; for (int i=1;i<=n;i++) { cin >> a[i]; } a[n+1]=10000000000; for (int i=1;i<=m;i++) { cin >> b[i]; } dp[0]=1; thua[0]=a[1]; vt[0]=1; for (int i=1;i<=(1<<m);i++) { for (int i2=1;i2<=m;i2++) { if (!(i&(1<<(i2-1)))) continue; tong[i]+=b[i2]; } } for (int i=1;i<=(1<<m);i++) { long long tong2=0; for (int i2=1;i2<=n+1;i2++) { tong2=tong2+a[i2]; if (tong2>tong[i]) { vt[i]=i2; thua[i]=tong2-tong[i]; break; } } } for (int i=1;i<=(1<<m);i++) { for (int i2=1;i2<=m;i2++) { if (!(i&(1<<(i2-1)))) continue; int bit=i^(1<<(i2-1)); if (dp[bit]==0) continue; if (thua[bit]>=b[i2]) { dp[i]=1; } } } // cout << vt[9] << " " << thua[9] << " " << tong[9] << " " << dp[9] << '\n'; for (int i=1;i<=(1<<m);i++) { if ((dp[i]) and (vt[i]==n+1)) { // cout << i << '\n'; cout << "YES"; return 0; } } cout << "NO"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...