답안 #68470 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68470	2018-08-17T07:53:08 Z	tatatan	은행 (IZhO14_bank)	C++11	100 / 100	802 ms	18740 KB

bank

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

int vis[1<<20],n,mo,a[21],m[20],val[1<<20],x;
vector<int> v[20005],ans[21];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>mo;
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(int i=0;i<mo;++i)
		cin>>m[i];
	for(int i=0;i<(1<<mo);++i) {
		vis[i]=1;
		for(int j=0;j<mo;++j)
			if((1<<j)&i)
				val[i]+=m[j];
		v[val[i]].pb(i);
	}
	for(int i=1;i<=n;++i) {
		for(int j=0;j<v[a[i]].size();++j) {
			if(vis[v[a[i]][j]])
				ans[i].pb(v[a[i]][j]);
		}
		memset(vis,0,sizeof vis);
		queue<int> q;
		for(int j=0;j<ans[i].size();++j) {
			q.push(ans[i][j]);
			vis[ans[i][j]]=1;
		}
		while(!q.empty()) {
			x=q.front();
			q.pop();
			for(int j=0;j<mo;++j)
				if(!(x&(1<<j))&&!vis[x|(1<<j)]) {
					q.push(x|(1<<j));
					vis[x|(1<<j)]=1;
				}
		}
	}
	if(ans[n].size()) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;

}

Compilation message

bank.cpp: In function 'int main()':
bank.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[a[i]].size();++j) {
               ~^~~~~~~~~~~~~~~
bank.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<ans[i].size();++j) {
               ~^~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	5 ms	5116 KB	Output is correct
3	Correct	5 ms	5116 KB	Output is correct
4	Correct	9 ms	5316 KB	Output is correct
5	Correct	89 ms	15344 KB	Output is correct
6	Correct	5 ms	15344 KB	Output is correct
7	Correct	6 ms	15344 KB	Output is correct
8	Correct	128 ms	15372 KB	Output is correct
9	Correct	89 ms	15372 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	15372 KB	Output is correct
2	Correct	6 ms	15372 KB	Output is correct
3	Correct	6 ms	15372 KB	Output is correct
4	Correct	6 ms	15372 KB	Output is correct
5	Correct	7 ms	15372 KB	Output is correct
6	Correct	6 ms	15372 KB	Output is correct
7	Correct	6 ms	15372 KB	Output is correct
8	Correct	6 ms	15372 KB	Output is correct
9	Correct	6 ms	15372 KB	Output is correct
10	Correct	6 ms	15372 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	15372 KB	Output is correct
2	Correct	8 ms	15372 KB	Output is correct
3	Correct	10 ms	15372 KB	Output is correct
4	Correct	10 ms	15372 KB	Output is correct
5	Correct	9 ms	15372 KB	Output is correct
6	Correct	8 ms	15372 KB	Output is correct
7	Correct	8 ms	15372 KB	Output is correct
8	Correct	7 ms	15372 KB	Output is correct
9	Correct	9 ms	15372 KB	Output is correct
10	Correct	8 ms	15372 KB	Output is correct
11	Correct	9 ms	15372 KB	Output is correct

Subtask #4
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	5 ms	5116 KB	Output is correct
3	Correct	5 ms	5116 KB	Output is correct
4	Correct	9 ms	5316 KB	Output is correct
5	Correct	89 ms	15344 KB	Output is correct
6	Correct	5 ms	15344 KB	Output is correct
7	Correct	6 ms	15344 KB	Output is correct
8	Correct	128 ms	15372 KB	Output is correct
9	Correct	89 ms	15372 KB	Output is correct
10	Correct	6 ms	15372 KB	Output is correct
11	Correct	6 ms	15372 KB	Output is correct
12	Correct	6 ms	15372 KB	Output is correct
13	Correct	6 ms	15372 KB	Output is correct
14	Correct	7 ms	15372 KB	Output is correct
15	Correct	6 ms	15372 KB	Output is correct
16	Correct	6 ms	15372 KB	Output is correct
17	Correct	6 ms	15372 KB	Output is correct
18	Correct	6 ms	15372 KB	Output is correct
19	Correct	6 ms	15372 KB	Output is correct
20	Correct	9 ms	15372 KB	Output is correct
21	Correct	8 ms	15372 KB	Output is correct
22	Correct	10 ms	15372 KB	Output is correct
23	Correct	10 ms	15372 KB	Output is correct
24	Correct	9 ms	15372 KB	Output is correct
25	Correct	8 ms	15372 KB	Output is correct
26	Correct	8 ms	15372 KB	Output is correct
27	Correct	7 ms	15372 KB	Output is correct
28	Correct	9 ms	15372 KB	Output is correct
29	Correct	8 ms	15372 KB	Output is correct
30	Correct	9 ms	15372 KB	Output is correct
31	Correct	130 ms	15924 KB	Output is correct
32	Correct	157 ms	15924 KB	Output is correct
33	Correct	170 ms	15924 KB	Output is correct
34	Correct	169 ms	15924 KB	Output is correct
35	Correct	178 ms	16208 KB	Output is correct
36	Correct	177 ms	16208 KB	Output is correct
37	Correct	119 ms	16208 KB	Output is correct
38	Correct	92 ms	16208 KB	Output is correct
39	Correct	727 ms	16208 KB	Output is correct
40	Correct	105 ms	16208 KB	Output is correct
41	Correct	105 ms	16208 KB	Output is correct
42	Correct	227 ms	16208 KB	Output is correct
43	Correct	139 ms	16224 KB	Output is correct
44	Correct	98 ms	16296 KB	Output is correct
45	Correct	233 ms	16296 KB	Output is correct
46	Correct	183 ms	16608 KB	Output is correct
47	Correct	136 ms	16608 KB	Output is correct
48	Correct	155 ms	16608 KB	Output is correct
49	Correct	85 ms	16608 KB	Output is correct
50	Correct	694 ms	17832 KB	Output is correct
51	Correct	242 ms	17832 KB	Output is correct
52	Correct	329 ms	17832 KB	Output is correct
53	Correct	321 ms	17832 KB	Output is correct
54	Correct	746 ms	17832 KB	Output is correct
55	Correct	692 ms	17832 KB	Output is correct
56	Correct	802 ms	18740 KB	Output is correct
57	Correct	714 ms	18740 KB	Output is correct
58	Correct	722 ms	18740 KB	Output is correct

답안 #68470

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