Submission #33602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
33602	2017-10-30T10:45:05 Z	RockyB	Bank (IZhO14_bank)	C++14	100 / 100	398 ms	179092 KB

bank

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
int a[N], b[N];

int sum[N];

namespace s12 {
	void rec(int v = 1) {
		if (v > m) {
			for (int i = 1; i <= n; i++) {
				if (sum[i] != a[i]) {
					return;
				}
			}
			cout << "YES";
			ioi
		}
		rec(v + 1);
		for (int i = 1; i <= n; i++) {
			if (sum[i] + b[v] <= a[i]) {
				sum[i] += b[v];
				rec(v + 1);
				sum[i] -= b[v];
			}
		}
	}
	void solve() {
		rec();
		cout << "NO";
		ioi
	}
}
namespace s3 {
	vector <int> good[1111];
	void rec(int v = 1, int sum = 0, int mask = 0) {
		if (sum > 1000) return;
		if (v > m) {
			good[sum].pb(mask);
			return;
		}
		rec(v + 1, sum, mask);
		rec(v + 1, sum + b[v], mask | (1 << (v - 1)));
	}
	int dp[21][1 << 21];
	int calc(int v = 1, int mask = (1 << m) - 1) {
		if (v > n) return 1;
		if (~dp[v][mask]) return dp[v][mask];
		for (auto it : good[a[v]]) {
			if ((mask | it) == mask) {
				if (calc(v + 1, mask ^ it)) return dp[v][mask] = 1;
			}
		}
		return dp[v][mask] = 0;
	}
	void solve() {
		rec();	
		memset(dp, -1, sizeof(dp));
		if (calc()) cout << "YES";
		else cout << "NO";
		ioi
	}
}


int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> m;
	if (n > m) cout << "NO", ioi
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	s3 :: solve();
	if (n == 1 || max(n, m) <= 10) s12 :: solve();

	ioi
}

Subtask #1
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	172792 KB	Output is correct
2	Correct	135 ms	173088 KB	Output is correct
3	Correct	134 ms	173088 KB	Output is correct
4	Correct	137 ms	173088 KB	Output is correct
5	Correct	151 ms	179092 KB	Output is correct
6	Correct	136 ms	179092 KB	Output is correct
7	Correct	140 ms	179092 KB	Output is correct
8	Correct	156 ms	179092 KB	Output is correct
9	Correct	149 ms	179092 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	179092 KB	Output is correct
2	Correct	133 ms	179092 KB	Output is correct
3	Correct	134 ms	179092 KB	Output is correct
4	Correct	136 ms	179092 KB	Output is correct
5	Correct	134 ms	179092 KB	Output is correct
6	Correct	134 ms	179092 KB	Output is correct
7	Correct	136 ms	179092 KB	Output is correct
8	Correct	135 ms	179092 KB	Output is correct
9	Correct	132 ms	179092 KB	Output is correct
10	Correct	134 ms	179092 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	179092 KB	Output is correct
2	Correct	135 ms	179092 KB	Output is correct
3	Correct	119 ms	179092 KB	Output is correct
4	Correct	115 ms	179092 KB	Output is correct
5	Correct	120 ms	179092 KB	Output is correct
6	Correct	117 ms	179092 KB	Output is correct
7	Correct	120 ms	179092 KB	Output is correct
8	Correct	124 ms	179092 KB	Output is correct
9	Correct	118 ms	179092 KB	Output is correct
10	Correct	142 ms	179092 KB	Output is correct
11	Correct	156 ms	179092 KB	Output is correct

Subtask #4
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	172792 KB	Output is correct
2	Correct	135 ms	173088 KB	Output is correct
3	Correct	134 ms	173088 KB	Output is correct
4	Correct	137 ms	173088 KB	Output is correct
5	Correct	151 ms	179092 KB	Output is correct
6	Correct	136 ms	179092 KB	Output is correct
7	Correct	140 ms	179092 KB	Output is correct
8	Correct	156 ms	179092 KB	Output is correct
9	Correct	149 ms	179092 KB	Output is correct
10	Correct	134 ms	179092 KB	Output is correct
11	Correct	133 ms	179092 KB	Output is correct
12	Correct	134 ms	179092 KB	Output is correct
13	Correct	136 ms	179092 KB	Output is correct
14	Correct	134 ms	179092 KB	Output is correct
15	Correct	134 ms	179092 KB	Output is correct
16	Correct	136 ms	179092 KB	Output is correct
17	Correct	135 ms	179092 KB	Output is correct
18	Correct	132 ms	179092 KB	Output is correct
19	Correct	134 ms	179092 KB	Output is correct
20	Correct	133 ms	179092 KB	Output is correct
21	Correct	135 ms	179092 KB	Output is correct
22	Correct	119 ms	179092 KB	Output is correct
23	Correct	115 ms	179092 KB	Output is correct
24	Correct	120 ms	179092 KB	Output is correct
25	Correct	117 ms	179092 KB	Output is correct
26	Correct	120 ms	179092 KB	Output is correct
27	Correct	124 ms	179092 KB	Output is correct
28	Correct	118 ms	179092 KB	Output is correct
29	Correct	142 ms	179092 KB	Output is correct
30	Correct	156 ms	179092 KB	Output is correct
31	Correct	130 ms	179092 KB	Output is correct
32	Correct	129 ms	179092 KB	Output is correct
33	Correct	120 ms	179092 KB	Output is correct
34	Correct	133 ms	179092 KB	Output is correct
35	Correct	129 ms	179092 KB	Output is correct
36	Correct	134 ms	179092 KB	Output is correct
37	Correct	135 ms	179092 KB	Output is correct
38	Correct	130 ms	179092 KB	Output is correct
39	Correct	138 ms	179092 KB	Output is correct
40	Correct	140 ms	179092 KB	Output is correct
41	Correct	119 ms	179092 KB	Output is correct
42	Correct	133 ms	179092 KB	Output is correct
43	Correct	122 ms	179092 KB	Output is correct
44	Correct	117 ms	179092 KB	Output is correct
45	Correct	132 ms	179092 KB	Output is correct
46	Correct	145 ms	179092 KB	Output is correct
47	Correct	117 ms	179092 KB	Output is correct
48	Correct	151 ms	179092 KB	Output is correct
49	Correct	152 ms	179092 KB	Output is correct
50	Correct	240 ms	179092 KB	Output is correct
51	Correct	151 ms	179092 KB	Output is correct
52	Correct	149 ms	179092 KB	Output is correct
53	Correct	398 ms	179092 KB	Output is correct
54	Correct	264 ms	179092 KB	Output is correct
55	Correct	240 ms	179092 KB	Output is correct
56	Correct	231 ms	179092 KB	Output is correct
57	Correct	257 ms	179092 KB	Output is correct
58	Correct	167 ms	179092 KB	Output is correct

Submission #33602

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 25.0 / 25.0

Subtask #3 27.0 / 27.0

Subtask #4 29.0 / 29.0

Subtask #1
19.0 / 19.0

Subtask #2
25.0 / 25.0

Subtask #3
27.0 / 27.0

Subtask #4
29.0 / 29.0