Submission #20372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20372	2017-02-07T09:47:40 Z		복불복 (OJUZ11_luck)	C++	13 / 100	259 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	780 KB	Output isn't correct
3	Correct	3 ms	780 KB	Output is correct
4	Incorrect	4 ms	780 KB	Output isn't correct
5	Correct	4 ms	780 KB	Output is correct
6	Correct	4 ms	780 KB	Output is correct
7	Correct	1 ms	780 KB	Output is correct
8	Correct	2 ms	780 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Incorrect	4 ms	780 KB	Output isn't correct
11	Incorrect	3 ms	780 KB	Output isn't correct
12	Correct	1 ms	780 KB	Output is correct
13	Correct	1 ms	780 KB	Output is correct
14	Correct	2 ms	780 KB	Output is correct
15	Correct	2 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	3 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	840 KB	Output is correct
20	Correct	1 ms	840 KB	Output is correct
21	Correct	3 ms	840 KB	Output is correct
22	Correct	1 ms	840 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	840 KB	Output is correct
2	Correct	2 ms	840 KB	Output is correct
3	Correct	2 ms	840 KB	Output is correct
4	Correct	2 ms	840 KB	Output is correct
5	Correct	2 ms	840 KB	Output is correct
6	Correct	2 ms	840 KB	Output is correct
7	Correct	2 ms	840 KB	Output is correct
8	Correct	2 ms	840 KB	Output is correct
9	Correct	2 ms	840 KB	Output is correct
10	Correct	1 ms	840 KB	Output is correct
11	Correct	1 ms	840 KB	Output is correct
12	Correct	1 ms	840 KB	Output is correct
13	Correct	1 ms	840 KB	Output is correct
14	Correct	2 ms	840 KB	Output is correct
15	Correct	2 ms	840 KB	Output is correct
16	Correct	1 ms	840 KB	Output is correct
17	Correct	2 ms	840 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	780 KB	Output isn't correct
3	Correct	3 ms	780 KB	Output is correct
4	Incorrect	4 ms	780 KB	Output isn't correct
5	Correct	4 ms	780 KB	Output is correct
6	Correct	4 ms	780 KB	Output is correct
7	Correct	1 ms	780 KB	Output is correct
8	Correct	2 ms	780 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Incorrect	4 ms	780 KB	Output isn't correct
11	Incorrect	3 ms	780 KB	Output isn't correct
12	Correct	1 ms	780 KB	Output is correct
13	Correct	1 ms	780 KB	Output is correct
14	Correct	2 ms	780 KB	Output is correct
15	Correct	2 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	3 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	840 KB	Output is correct
20	Correct	1 ms	840 KB	Output is correct
21	Correct	3 ms	840 KB	Output is correct
22	Correct	1 ms	840 KB	Output is correct
23	Incorrect	24 ms	840 KB	Output isn't correct
24	Incorrect	34 ms	840 KB	Output isn't correct
25	Incorrect	48 ms	840 KB	Output isn't correct
26	Incorrect	14 ms	840 KB	Output isn't correct
27	Incorrect	66 ms	840 KB	Output isn't correct
28	Incorrect	92 ms	840 KB	Output isn't correct
29	Incorrect	59 ms	840 KB	Output isn't correct
30	Incorrect	223 ms	856 KB	Output isn't correct
31	Incorrect	83 ms	856 KB	Output isn't correct
32	Incorrect	11 ms	856 KB	Output isn't correct
33	Incorrect	99 ms	856 KB	Output isn't correct
34	Incorrect	259 ms	856 KB	Output isn't correct
35	Incorrect	72 ms	856 KB	Output isn't correct
36	Incorrect	15 ms	856 KB	Output isn't correct
37	Incorrect	23 ms	856 KB	Output isn't correct
38	Incorrect	18 ms	856 KB	Output isn't correct
39	Correct	1 ms	856 KB	Output is correct
40	Correct	2 ms	856 KB	Output is correct
41	Correct	9 ms	856 KB	Output is correct
42	Correct	3 ms	856 KB	Output is correct
43	Incorrect	7 ms	856 KB	Output isn't correct
44	Incorrect	13 ms	856 KB	Output isn't correct
45	Correct	1 ms	856 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	780 KB	Output isn't correct
3	Correct	3 ms	780 KB	Output is correct
4	Incorrect	4 ms	780 KB	Output isn't correct
5	Correct	4 ms	780 KB	Output is correct
6	Correct	4 ms	780 KB	Output is correct
7	Correct	1 ms	780 KB	Output is correct
8	Correct	2 ms	780 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Incorrect	4 ms	780 KB	Output isn't correct
11	Incorrect	3 ms	780 KB	Output isn't correct
12	Correct	1 ms	780 KB	Output is correct
13	Correct	1 ms	780 KB	Output is correct
14	Correct	2 ms	780 KB	Output is correct
15	Correct	2 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	3 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	840 KB	Output is correct
20	Correct	1 ms	840 KB	Output is correct
21	Correct	3 ms	840 KB	Output is correct
22	Correct	1 ms	840 KB	Output is correct
23	Correct	2 ms	840 KB	Output is correct
24	Correct	2 ms	840 KB	Output is correct
25	Correct	2 ms	840 KB	Output is correct
26	Correct	2 ms	840 KB	Output is correct
27	Correct	2 ms	840 KB	Output is correct
28	Correct	2 ms	840 KB	Output is correct
29	Correct	2 ms	840 KB	Output is correct
30	Correct	2 ms	840 KB	Output is correct
31	Correct	2 ms	840 KB	Output is correct
32	Correct	1 ms	840 KB	Output is correct
33	Correct	1 ms	840 KB	Output is correct
34	Correct	1 ms	840 KB	Output is correct
35	Correct	1 ms	840 KB	Output is correct
36	Correct	2 ms	840 KB	Output is correct
37	Correct	2 ms	840 KB	Output is correct
38	Correct	1 ms	840 KB	Output is correct
39	Correct	2 ms	840 KB	Output is correct
40	Incorrect	24 ms	840 KB	Output isn't correct
41	Incorrect	34 ms	840 KB	Output isn't correct
42	Incorrect	48 ms	840 KB	Output isn't correct
43	Incorrect	14 ms	840 KB	Output isn't correct
44	Incorrect	66 ms	840 KB	Output isn't correct
45	Incorrect	92 ms	840 KB	Output isn't correct
46	Incorrect	59 ms	840 KB	Output isn't correct
47	Incorrect	223 ms	856 KB	Output isn't correct
48	Incorrect	83 ms	856 KB	Output isn't correct
49	Incorrect	11 ms	856 KB	Output isn't correct
50	Incorrect	99 ms	856 KB	Output isn't correct
51	Incorrect	259 ms	856 KB	Output isn't correct
52	Incorrect	72 ms	856 KB	Output isn't correct
53	Incorrect	15 ms	856 KB	Output isn't correct
54	Incorrect	23 ms	856 KB	Output isn't correct
55	Incorrect	18 ms	856 KB	Output isn't correct
56	Correct	1 ms	856 KB	Output is correct
57	Correct	2 ms	856 KB	Output is correct
58	Correct	9 ms	856 KB	Output is correct
59	Correct	3 ms	856 KB	Output is correct
60	Incorrect	7 ms	856 KB	Output isn't correct
61	Incorrect	13 ms	856 KB	Output isn't correct
62	Correct	1 ms	856 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	1552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	4 ms	1584 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	780 KB	Output isn't correct
3	Correct	3 ms	780 KB	Output is correct
4	Incorrect	4 ms	780 KB	Output isn't correct
5	Correct	4 ms	780 KB	Output is correct
6	Correct	4 ms	780 KB	Output is correct
7	Correct	1 ms	780 KB	Output is correct
8	Correct	2 ms	780 KB	Output is correct
9	Correct	3 ms	780 KB	Output is correct
10	Incorrect	4 ms	780 KB	Output isn't correct
11	Incorrect	3 ms	780 KB	Output isn't correct
12	Correct	1 ms	780 KB	Output is correct
13	Correct	1 ms	780 KB	Output is correct
14	Correct	2 ms	780 KB	Output is correct
15	Correct	2 ms	780 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	3 ms	780 KB	Output is correct
18	Correct	3 ms	780 KB	Output is correct
19	Correct	3 ms	840 KB	Output is correct
20	Correct	1 ms	840 KB	Output is correct
21	Correct	3 ms	840 KB	Output is correct
22	Correct	1 ms	840 KB	Output is correct
23	Correct	2 ms	840 KB	Output is correct
24	Correct	2 ms	840 KB	Output is correct
25	Correct	2 ms	840 KB	Output is correct
26	Correct	2 ms	840 KB	Output is correct
27	Correct	2 ms	840 KB	Output is correct
28	Correct	2 ms	840 KB	Output is correct
29	Correct	2 ms	840 KB	Output is correct
30	Correct	2 ms	840 KB	Output is correct
31	Correct	2 ms	840 KB	Output is correct
32	Correct	1 ms	840 KB	Output is correct
33	Correct	1 ms	840 KB	Output is correct
34	Correct	1 ms	840 KB	Output is correct
35	Correct	1 ms	840 KB	Output is correct
36	Correct	2 ms	840 KB	Output is correct
37	Correct	2 ms	840 KB	Output is correct
38	Correct	1 ms	840 KB	Output is correct
39	Correct	2 ms	840 KB	Output is correct
40	Incorrect	24 ms	840 KB	Output isn't correct
41	Incorrect	34 ms	840 KB	Output isn't correct
42	Incorrect	48 ms	840 KB	Output isn't correct
43	Incorrect	14 ms	840 KB	Output isn't correct
44	Incorrect	66 ms	840 KB	Output isn't correct
45	Incorrect	92 ms	840 KB	Output isn't correct
46	Incorrect	59 ms	840 KB	Output isn't correct
47	Incorrect	223 ms	856 KB	Output isn't correct
48	Incorrect	83 ms	856 KB	Output isn't correct
49	Incorrect	11 ms	856 KB	Output isn't correct
50	Incorrect	99 ms	856 KB	Output isn't correct
51	Incorrect	259 ms	856 KB	Output isn't correct
52	Incorrect	72 ms	856 KB	Output isn't correct
53	Incorrect	15 ms	856 KB	Output isn't correct
54	Incorrect	23 ms	856 KB	Output isn't correct
55	Incorrect	18 ms	856 KB	Output isn't correct
56	Correct	1 ms	856 KB	Output is correct
57	Correct	2 ms	856 KB	Output is correct
58	Correct	9 ms	856 KB	Output is correct
59	Correct	3 ms	856 KB	Output is correct
60	Incorrect	7 ms	856 KB	Output isn't correct
61	Incorrect	13 ms	856 KB	Output isn't correct
62	Correct	1 ms	856 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	1552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	6 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	5 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	3 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	6 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	3 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
93	Runtime error	4 ms	1584 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	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
98	Runtime error	5 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	3 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	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
104	Runtime error	3 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
105	Runtime error	6 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
106	Runtime error	4 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
107	Runtime error	6 ms	1584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Submission #20372

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