oj.uz

Submission #71664

# Submission time Handle Problem Language Result Execution time Memory
71664 2018-08-25T10:25:41 Z istlemin Bank (IZhO14_bank) C++14
25 / 100
 378 ms 2268 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

int main(){
	cin.sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
    vi a(n);
    vi b(m);
    rep(i,0,n) cin>>a[i];
    rep(i,0,m) cin>>b[i];

    if(m<=10&&n<=10){
		a.push_back(0);
		vector<vector<vector<bool> > > dp(n+1,vector<vector<bool> >(1001,vector<bool>(1<<m,true)));//dp[index][left][mask];

		for(ll index = n-1;index>=0;index--){
			rep(mask,0,(1<<m))
				dp[index][0][mask] = dp[index+1][a[index+1]][mask];
			rep(left,0,1001){
				rep(mask,0,(1<<m)){
					dp[index][left][mask] = false;
					if(left==0)
						dp[index][left][mask] = dp[index+1][a[index+1]][mask];
					//cout<<index<<" "<<left<<" ";
					rep(i,0,m){
						//cout<<((mask&(1<<i))>0);
						dp[index][left][mask] = dp[index][left][mask]||((mask&(1<<i))==0&&left>=b[i]&&dp[index][left-b[i]][mask|(1<<i)]);
					}
					//cout<<": "<<dp[index][left][mask]<<endl;
				}
			}
		}

		if(dp[0][a[0]][0]){
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	} else if(n==1&&m<=20){
        bool works = false;
        rep(mask,0,(1<<m)){
			ll sum = 0;
			rep(i,0,m){
                if((1<<m)&mask) sum += b[i];
			}
			works |= (sum==a[0]);
        }

		if(works){
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	}
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 54 ms 960 KB Output is correct
4 Incorrect 2 ms 960 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 1672 KB Output is correct
2 Correct 161 ms 1672 KB Output is correct
3 Correct 110 ms 1672 KB Output is correct
4 Correct 214 ms 1672 KB Output is correct
5 Correct 378 ms 2268 KB Output is correct
6 Correct 266 ms 2268 KB Output is correct
7 Correct 162 ms 2268 KB Output is correct
8 Correct 215 ms 2268 KB Output is correct
9 Correct 163 ms 2268 KB Output is correct
10 Correct 266 ms 2268 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 54 ms 960 KB Output is correct
4 Incorrect 2 ms 960 KB Output isn't correct
5 Halted 0 ms 0 KB -