oj.uz

Submission #71661

# Submission time Handle Problem Language Result Execution time Memory
71661 2018-08-25T10:23:35 Z istlemin Bank (IZhO14_bank) C++14
25 / 100
 1000 ms 19168 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];

	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;
    }
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 69 ms 960 KB Output is correct
4 Execution timed out 1082 ms 12572 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 12572 KB Output is correct
2 Correct 168 ms 12572 KB Output is correct
3 Correct 113 ms 12572 KB Output is correct
4 Correct 224 ms 12572 KB Output is correct
5 Correct 394 ms 12572 KB Output is correct
6 Correct 282 ms 12572 KB Output is correct
7 Correct 169 ms 12572 KB Output is correct
8 Correct 224 ms 12572 KB Output is correct
9 Correct 166 ms 12572 KB Output is correct
10 Correct 271 ms 12572 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 19168 KB Time limit exceeded
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 764 KB Output is correct
3 Correct 69 ms 960 KB Output is correct
4 Execution timed out 1082 ms 12572 KB Time limit exceeded
5 Halted 0 ms 0 KB -