Submission #20374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20374	2017-02-07T09:50:53 Z		복불복 (OJUZ11_luck)	C++	13 / 100	252 ms	1584 KB

luck

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
#define MOD (ll)(1e9+7)

int N,K;
const int MAX_N = 110;

int a[MAX_N],b[MAX_N],c[MAX_N][MAX_N];
int s[MAX_N],e[MAX_N];

ll dp[1<<16];
ll f(int x,int bit){
	if(x>N)return 1;
	ll& ret = dp[bit];
	if(~ret)return ret;
	ret=0;
	for(int i=s[x];i<=e[x];i++){
		if(bit>>i&1)continue;
		ret+=f(x+1,bit|(1<<i));
	}
	return ret;
}

int main(){

	scanf("%d%d",&N,&K);

	for(int i=1;i<=N;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+N+1);
	reverse(a+1,a+N+1);

	for(int j=1;j<=N;j++){
		scanf("%d",&b[j]);
	}
	sort(b+1,b+N+1);
	reverse(b+1,b+N+1);

	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			c[i][j]=a[i]+b[j];
		}
	}

	ll ans=0;
	if(K==1){
		for(int i=1;i<=N;i++){
			int p=i;
			ll sum=1;
			for(int j=2,k=p;j<=N;j++){
				while(k>0&&c[j][k]<=c[1][i])k--;
				p=k;
				sum*=(N-p-j+1);
				sum%=MOD;
			}
			ans+=sum;
			ans%=MOD;
		}
		printf("%lld\n",ans);
	}else{
		for(int i=1;i<=K;i++){
			for(int j=1;j<=N;j++){
				for(int k=1;k<=K;k++){
					if(k==i){
						s[k]=e[k]=j;
						continue;
					}
					int p=N;
					while(p>0&&c[k][p]<=c[i][j])p--;
					s[k]=1,e[k]=p;
				}
				for(int k=K+1;k<=N;k++){
					int p=N;
					while(p>0&&c[k][p]<=c[i][j])p--;
					s[k]=p+1,e[k]=N;
				}

				memset(dp,-1,sizeof(dp));
				ans+=f(1,0);
			}
		}
		printf("%lld\n",ans);
	}

	return 0;
}

Compilation message

luck.cpp: In function 'int main()':
luck.cpp:29:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&K);
                     ^
luck.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
luck.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[j]);
                    ^

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Incorrect	3 ms	768 KB	Output isn't correct
3	Correct	3 ms	768 KB	Output is correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	4 ms	828 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	828 KB	Output is correct
9	Correct	2 ms	828 KB	Output is correct
10	Incorrect	2 ms	828 KB	Output isn't correct
11	Incorrect	3 ms	828 KB	Output isn't correct
12	Correct	2 ms	828 KB	Output is correct
13	Correct	1 ms	828 KB	Output is correct
14	Correct	1 ms	828 KB	Output is correct
15	Correct	2 ms	828 KB	Output is correct
16	Correct	2 ms	828 KB	Output is correct
17	Correct	3 ms	828 KB	Output is correct
18	Correct	3 ms	828 KB	Output is correct
19	Correct	2 ms	828 KB	Output is correct
20	Correct	1 ms	828 KB	Output is correct
21	Correct	3 ms	828 KB	Output is correct
22	Correct	2 ms	828 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	828 KB	Output is correct
2	Correct	1 ms	828 KB	Output is correct
3	Correct	2 ms	828 KB	Output is correct
4	Correct	2 ms	828 KB	Output is correct
5	Correct	2 ms	828 KB	Output is correct
6	Correct	2 ms	828 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	828 KB	Output is correct
9	Correct	2 ms	828 KB	Output is correct
10	Correct	1 ms	828 KB	Output is correct
11	Correct	2 ms	828 KB	Output is correct
12	Correct	1 ms	828 KB	Output is correct
13	Correct	2 ms	828 KB	Output is correct
14	Correct	2 ms	828 KB	Output is correct
15	Correct	1 ms	828 KB	Output is correct
16	Correct	2 ms	828 KB	Output is correct
17	Correct	1 ms	828 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Incorrect	3 ms	768 KB	Output isn't correct
3	Correct	3 ms	768 KB	Output is correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	4 ms	828 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	828 KB	Output is correct
9	Correct	2 ms	828 KB	Output is correct
10	Incorrect	2 ms	828 KB	Output isn't correct
11	Incorrect	3 ms	828 KB	Output isn't correct
12	Correct	2 ms	828 KB	Output is correct
13	Correct	1 ms	828 KB	Output is correct
14	Correct	1 ms	828 KB	Output is correct
15	Correct	2 ms	828 KB	Output is correct
16	Correct	2 ms	828 KB	Output is correct
17	Correct	3 ms	828 KB	Output is correct
18	Correct	3 ms	828 KB	Output is correct
19	Correct	2 ms	828 KB	Output is correct
20	Correct	1 ms	828 KB	Output is correct
21	Correct	3 ms	828 KB	Output is correct
22	Correct	2 ms	828 KB	Output is correct
23	Incorrect	28 ms	828 KB	Output isn't correct
24	Incorrect	34 ms	852 KB	Output isn't correct
25	Incorrect	45 ms	852 KB	Output isn't correct
26	Incorrect	13 ms	852 KB	Output isn't correct
27	Incorrect	50 ms	852 KB	Output isn't correct
28	Incorrect	89 ms	852 KB	Output isn't correct
29	Incorrect	56 ms	852 KB	Output isn't correct
30	Incorrect	216 ms	852 KB	Output isn't correct
31	Incorrect	83 ms	852 KB	Output isn't correct
32	Incorrect	11 ms	852 KB	Output isn't correct
33	Incorrect	97 ms	852 KB	Output isn't correct
34	Incorrect	252 ms	852 KB	Output isn't correct
35	Incorrect	73 ms	852 KB	Output isn't correct
36	Incorrect	13 ms	852 KB	Output isn't correct
37	Incorrect	25 ms	852 KB	Output isn't correct
38	Incorrect	14 ms	852 KB	Output isn't correct
39	Correct	2 ms	852 KB	Output is correct
40	Correct	1 ms	852 KB	Output is correct
41	Correct	9 ms	852 KB	Output is correct
42	Correct	3 ms	852 KB	Output is correct
43	Incorrect	7 ms	852 KB	Output isn't correct
44	Incorrect	14 ms	852 KB	Output isn't correct
45	Correct	2 ms	852 KB	Output is correct

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Incorrect	3 ms	768 KB	Output isn't correct
3	Correct	3 ms	768 KB	Output is correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	4 ms	828 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	828 KB	Output is correct
9	Correct	2 ms	828 KB	Output is correct
10	Incorrect	2 ms	828 KB	Output isn't correct
11	Incorrect	3 ms	828 KB	Output isn't correct
12	Correct	2 ms	828 KB	Output is correct
13	Correct	1 ms	828 KB	Output is correct
14	Correct	1 ms	828 KB	Output is correct
15	Correct	2 ms	828 KB	Output is correct
16	Correct	2 ms	828 KB	Output is correct
17	Correct	3 ms	828 KB	Output is correct
18	Correct	3 ms	828 KB	Output is correct
19	Correct	2 ms	828 KB	Output is correct
20	Correct	1 ms	828 KB	Output is correct
21	Correct	3 ms	828 KB	Output is correct
22	Correct	2 ms	828 KB	Output is correct
23	Correct	2 ms	828 KB	Output is correct
24	Correct	1 ms	828 KB	Output is correct
25	Correct	2 ms	828 KB	Output is correct
26	Correct	2 ms	828 KB	Output is correct
27	Correct	2 ms	828 KB	Output is correct
28	Correct	2 ms	828 KB	Output is correct
29	Correct	2 ms	828 KB	Output is correct
30	Correct	2 ms	828 KB	Output is correct
31	Correct	2 ms	828 KB	Output is correct
32	Correct	1 ms	828 KB	Output is correct
33	Correct	2 ms	828 KB	Output is correct
34	Correct	1 ms	828 KB	Output is correct
35	Correct	2 ms	828 KB	Output is correct
36	Correct	2 ms	828 KB	Output is correct
37	Correct	1 ms	828 KB	Output is correct
38	Correct	2 ms	828 KB	Output is correct
39	Correct	1 ms	828 KB	Output is correct
40	Incorrect	28 ms	828 KB	Output isn't correct
41	Incorrect	34 ms	852 KB	Output isn't correct
42	Incorrect	45 ms	852 KB	Output isn't correct
43	Incorrect	13 ms	852 KB	Output isn't correct
44	Incorrect	50 ms	852 KB	Output isn't correct
45	Incorrect	89 ms	852 KB	Output isn't correct
46	Incorrect	56 ms	852 KB	Output isn't correct
47	Incorrect	216 ms	852 KB	Output isn't correct
48	Incorrect	83 ms	852 KB	Output isn't correct
49	Incorrect	11 ms	852 KB	Output isn't correct
50	Incorrect	97 ms	852 KB	Output isn't correct
51	Incorrect	252 ms	852 KB	Output isn't correct
52	Incorrect	73 ms	852 KB	Output isn't correct
53	Incorrect	13 ms	852 KB	Output isn't correct
54	Incorrect	25 ms	852 KB	Output isn't correct
55	Incorrect	14 ms	852 KB	Output isn't correct
56	Correct	2 ms	852 KB	Output is correct
57	Correct	1 ms	852 KB	Output is correct
58	Correct	9 ms	852 KB	Output is correct
59	Correct	3 ms	852 KB	Output is correct
60	Incorrect	7 ms	852 KB	Output isn't correct
61	Incorrect	14 ms	852 KB	Output isn't correct
62	Correct	2 ms	852 KB	Output is correct
63	Runtime error	3 ms	1436 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	3 ms	1568 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	2 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	2 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Incorrect	3 ms	768 KB	Output isn't correct
3	Correct	3 ms	768 KB	Output is correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	4 ms	828 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	828 KB	Output is correct
9	Correct	2 ms	828 KB	Output is correct
10	Incorrect	2 ms	828 KB	Output isn't correct
11	Incorrect	3 ms	828 KB	Output isn't correct
12	Correct	2 ms	828 KB	Output is correct
13	Correct	1 ms	828 KB	Output is correct
14	Correct	1 ms	828 KB	Output is correct
15	Correct	2 ms	828 KB	Output is correct
16	Correct	2 ms	828 KB	Output is correct
17	Correct	3 ms	828 KB	Output is correct
18	Correct	3 ms	828 KB	Output is correct
19	Correct	2 ms	828 KB	Output is correct
20	Correct	1 ms	828 KB	Output is correct
21	Correct	3 ms	828 KB	Output is correct
22	Correct	2 ms	828 KB	Output is correct
23	Correct	2 ms	828 KB	Output is correct
24	Correct	1 ms	828 KB	Output is correct
25	Correct	2 ms	828 KB	Output is correct
26	Correct	2 ms	828 KB	Output is correct
27	Correct	2 ms	828 KB	Output is correct
28	Correct	2 ms	828 KB	Output is correct
29	Correct	2 ms	828 KB	Output is correct
30	Correct	2 ms	828 KB	Output is correct
31	Correct	2 ms	828 KB	Output is correct
32	Correct	1 ms	828 KB	Output is correct
33	Correct	2 ms	828 KB	Output is correct
34	Correct	1 ms	828 KB	Output is correct
35	Correct	2 ms	828 KB	Output is correct
36	Correct	2 ms	828 KB	Output is correct
37	Correct	1 ms	828 KB	Output is correct
38	Correct	2 ms	828 KB	Output is correct
39	Correct	1 ms	828 KB	Output is correct
40	Incorrect	28 ms	828 KB	Output isn't correct
41	Incorrect	34 ms	852 KB	Output isn't correct
42	Incorrect	45 ms	852 KB	Output isn't correct
43	Incorrect	13 ms	852 KB	Output isn't correct
44	Incorrect	50 ms	852 KB	Output isn't correct
45	Incorrect	89 ms	852 KB	Output isn't correct
46	Incorrect	56 ms	852 KB	Output isn't correct
47	Incorrect	216 ms	852 KB	Output isn't correct
48	Incorrect	83 ms	852 KB	Output isn't correct
49	Incorrect	11 ms	852 KB	Output isn't correct
50	Incorrect	97 ms	852 KB	Output isn't correct
51	Incorrect	252 ms	852 KB	Output isn't correct
52	Incorrect	73 ms	852 KB	Output isn't correct
53	Incorrect	13 ms	852 KB	Output isn't correct
54	Incorrect	25 ms	852 KB	Output isn't correct
55	Incorrect	14 ms	852 KB	Output isn't correct
56	Correct	2 ms	852 KB	Output is correct
57	Correct	1 ms	852 KB	Output is correct
58	Correct	9 ms	852 KB	Output is correct
59	Correct	3 ms	852 KB	Output is correct
60	Incorrect	7 ms	852 KB	Output isn't correct
61	Incorrect	14 ms	852 KB	Output isn't correct
62	Correct	2 ms	852 KB	Output is correct
63	Runtime error	3 ms	1436 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	3 ms	1568 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	2 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	2 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	6 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	5 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	7 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	4 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	3 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
93	Runtime error	5 ms	1572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
94	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
95	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
96	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
97	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
98	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
99	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
100	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
101	Runtime error	6 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
102	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
103	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
104	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
105	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
106	Runtime error	3 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
107	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Submission #20374

Compilation message

Subtask #1 0 / 9.0

Subtask #2 13.0 / 13.0

Subtask #3 0 / 25.0

Subtask #4 0 / 26.0

Subtask #5 0 / 27.0

Subtask #1
0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
0 / 25.0

Subtask #4
0 / 26.0

Subtask #5
0 / 27.0