oj.uz

Submission #675756

# Submission time Handle Problem Language Result Execution time Memory
675756 2022-12-27T19:52:41 Z vjudge1 Bank (IZhO14_bank) C++
52 / 100
 1000 ms 8524 KB 
/*
 * Author: fuad720
 * Time: 2022-12-27 23:33
 * Lang: C++
*/
#ifndef LOCAL
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)

#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
	cin.tie(0);

template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;

using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;


#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
	int n, m;
	cin >> n >> m;
	int a[n],b[m];
	rep(i,n)cin >> a[i];
	rep(i,m)cin >> b[i];
	vector<ll> bt[n];
	rep(i,(1<<m)) {
		int sum=0;
		rep(j,m) {
			if((1<<j)&i)
				sum+=b[j];
		}
		rep(j,n) {
			if(sum==a[j]){
				bt[j].pb(i);
			}
		}
	}
	int dp[n+1][(1<<m)];
	memset(dp,0,sizeof dp);
	rep(i,(1<<m))dp[0][i]=1;
	FOR(i,0,n) {
		rep(j,(1<<m)) {
			if(dp[i][j]==0)continue;
			for(int k:bt[i]) {
				if(k&j)continue;
				dp[i+1][j^k]|=dp[i][j];
			}
		}
	}
	cout << ((dp[n][(1<<m)-1])?"YES":"NO") << "\n";
}

int main () {
	FIO;
	int t=1;
	while(t--)
		solve();
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 488 KB Output is correct
5 Correct 31 ms 8508 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Execution timed out 1095 ms 8524 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 488 KB Output is correct
5 Correct 31 ms 8508 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Execution timed out 1095 ms 8524 KB Time limit exceeded
9 Halted 0 ms 0 KB -