# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
850638 | 2023-09-17T08:13:13 Z | askow | Bank (IZhO14_bank) | C++14 | 1000 ms | 41284 KB |
#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(false); cin.tie(0); //!!! dp[i][mask] da li je moguce u prvih i napraviti tako da iskoristim tacno mask bitove int n,m; cin>>n>>m; int a[n]; for(int i=0;i<n;i++)cin>>a[i]; int b[m]; for(int i=0;i<m;i++)cin>>b[i]; int dp[n+1][(1LL<<m)]; for(int i=0;i<=n;i++)for(int j=0;j<(1LL<<m);j++)dp[i][j]=0; for(int i=0;i<(1LL<<m);i++){ int R=0; for(int j=0;j<m;j++){ if(i&(1LL<<j))R+=b[j]; } if(R==a[0])dp[0][i]=1; } /* int ans=0; for(int i=0;i<(1LL<<m);i++)ans|=(dp[0][i]); if(ans)cout<<"YES"; else cout<<"NO";*/ int pref[(1LL<<m)]; for(int i=0;i<(1LL<<m);i++)pref[i]=0; for(int i=0;i<(1LL<<m);i++){ int R=0; for(int j=0;j<m;j++){ if(i&(1LL<<j))R+=b[j]; } pref[i]=R; } for(int i=1;i<n;i++){ //!!! dp[i][mask]|=dp[i-1][drugamaska]; //!!! i&j==0 nemaju zajednicki bit int R=0; for(int j=0;j<(1LL<<m);j++){ // za iti broj ces uzeti ovu masku if(pref[j]==a[i]){ //!!! ovu masku koristim da bi dobio a[i] //!!! sada me zanima dal mogu da od neke druge maske koja nema nijedan bit isti da dobijem sve i-1 brojeve for(int mask=0;mask<(1LL<<m);mask++){ if(mask&j)continue; dp[i][mask|j]|=(dp[i-1][mask]); } } } } int ans=0; for(int i=0;i<(1LL<<m);i++)ans|=dp[n-1][i]; if(ans)cout<<"YES"; else cout<<"NO"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 4 ms | 1116 KB | Output is correct |
5 | Correct | 140 ms | 24936 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 139 ms | 25032 KB | Output is correct |
9 | Correct | 140 ms | 24916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1372 KB | Output is correct |
2 | Correct | 2 ms | 884 KB | Output is correct |
3 | Correct | 3 ms | 1884 KB | Output is correct |
4 | Correct | 4 ms | 2396 KB | Output is correct |
5 | Correct | 3 ms | 1884 KB | Output is correct |
6 | Correct | 2 ms | 1116 KB | Output is correct |
7 | Correct | 2 ms | 1116 KB | Output is correct |
8 | Correct | 2 ms | 860 KB | Output is correct |
9 | Correct | 3 ms | 1628 KB | Output is correct |
10 | Correct | 4 ms | 1628 KB | Output is correct |
11 | Correct | 3 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 4 ms | 1116 KB | Output is correct |
5 | Correct | 140 ms | 24936 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 139 ms | 25032 KB | Output is correct |
9 | Correct | 140 ms | 24916 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 3 ms | 1372 KB | Output is correct |
21 | Correct | 2 ms | 884 KB | Output is correct |
22 | Correct | 3 ms | 1884 KB | Output is correct |
23 | Correct | 4 ms | 2396 KB | Output is correct |
24 | Correct | 3 ms | 1884 KB | Output is correct |
25 | Correct | 2 ms | 1116 KB | Output is correct |
26 | Correct | 2 ms | 1116 KB | Output is correct |
27 | Correct | 2 ms | 860 KB | Output is correct |
28 | Correct | 3 ms | 1628 KB | Output is correct |
29 | Correct | 4 ms | 1628 KB | Output is correct |
30 | Correct | 3 ms | 2396 KB | Output is correct |
31 | Correct | 902 ms | 33256 KB | Output is correct |
32 | Execution timed out | 1030 ms | 41284 KB | Time limit exceeded |
33 | Halted | 0 ms | 0 KB | - |