답안 #20375 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20375	2017-02-07T09:54:17 Z		복불복 (OJUZ11_luck)	C++	22 / 100	223 ms	1588 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;
					if(k>i)while(p>0&&c[k][p]<c[i][j])p--;
					else 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
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	700 KB	Output is correct
2	Correct	3 ms	700 KB	Output is correct
3	Correct	3 ms	720 KB	Output is correct
4	Correct	3 ms	720 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	4 ms	720 KB	Output is correct
7	Correct	1 ms	720 KB	Output is correct
8	Correct	2 ms	720 KB	Output is correct
9	Correct	2 ms	720 KB	Output is correct
10	Correct	3 ms	720 KB	Output is correct
11	Correct	3 ms	720 KB	Output is correct
12	Correct	2 ms	720 KB	Output is correct
13	Correct	2 ms	720 KB	Output is correct
14	Correct	1 ms	720 KB	Output is correct
15	Correct	3 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	784 KB	Output is correct
20	Correct	1 ms	784 KB	Output is correct
21	Correct	2 ms	784 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	784 KB	Output is correct
2	Correct	1 ms	784 KB	Output is correct
3	Correct	1 ms	784 KB	Output is correct
4	Correct	1 ms	784 KB	Output is correct
5	Correct	1 ms	784 KB	Output is correct
6	Correct	1 ms	784 KB	Output is correct
7	Correct	1 ms	784 KB	Output is correct
8	Correct	1 ms	784 KB	Output is correct
9	Correct	1 ms	784 KB	Output is correct
10	Correct	1 ms	784 KB	Output is correct
11	Correct	1 ms	784 KB	Output is correct
12	Correct	2 ms	784 KB	Output is correct
13	Correct	1 ms	784 KB	Output is correct
14	Correct	2 ms	784 KB	Output is correct
15	Correct	2 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	700 KB	Output is correct
2	Correct	3 ms	700 KB	Output is correct
3	Correct	3 ms	720 KB	Output is correct
4	Correct	3 ms	720 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	4 ms	720 KB	Output is correct
7	Correct	1 ms	720 KB	Output is correct
8	Correct	2 ms	720 KB	Output is correct
9	Correct	2 ms	720 KB	Output is correct
10	Correct	3 ms	720 KB	Output is correct
11	Correct	3 ms	720 KB	Output is correct
12	Correct	2 ms	720 KB	Output is correct
13	Correct	2 ms	720 KB	Output is correct
14	Correct	1 ms	720 KB	Output is correct
15	Correct	3 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	784 KB	Output is correct
20	Correct	1 ms	784 KB	Output is correct
21	Correct	2 ms	784 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Incorrect	27 ms	784 KB	Output isn't correct
24	Incorrect	42 ms	784 KB	Output isn't correct
25	Incorrect	44 ms	784 KB	Output isn't correct
26	Correct	15 ms	784 KB	Output is correct
27	Incorrect	50 ms	784 KB	Output isn't correct
28	Incorrect	93 ms	784 KB	Output isn't correct
29	Incorrect	54 ms	784 KB	Output isn't correct
30	Incorrect	204 ms	784 KB	Output isn't correct
31	Incorrect	70 ms	784 KB	Output isn't correct
32	Incorrect	10 ms	784 KB	Output isn't correct
33	Incorrect	82 ms	784 KB	Output isn't correct
34	Incorrect	223 ms	784 KB	Output isn't correct
35	Incorrect	71 ms	784 KB	Output isn't correct
36	Incorrect	11 ms	784 KB	Output isn't correct
37	Correct	22 ms	784 KB	Output is correct
38	Incorrect	15 ms	784 KB	Output isn't correct
39	Correct	1 ms	784 KB	Output is correct
40	Correct	2 ms	784 KB	Output is correct
41	Correct	11 ms	784 KB	Output is correct
42	Correct	3 ms	784 KB	Output is correct
43	Correct	7 ms	784 KB	Output is correct
44	Incorrect	13 ms	784 KB	Output isn't correct
45	Correct	2 ms	784 KB	Output is correct

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	700 KB	Output is correct
2	Correct	3 ms	700 KB	Output is correct
3	Correct	3 ms	720 KB	Output is correct
4	Correct	3 ms	720 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	4 ms	720 KB	Output is correct
7	Correct	1 ms	720 KB	Output is correct
8	Correct	2 ms	720 KB	Output is correct
9	Correct	2 ms	720 KB	Output is correct
10	Correct	3 ms	720 KB	Output is correct
11	Correct	3 ms	720 KB	Output is correct
12	Correct	2 ms	720 KB	Output is correct
13	Correct	2 ms	720 KB	Output is correct
14	Correct	1 ms	720 KB	Output is correct
15	Correct	3 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	784 KB	Output is correct
20	Correct	1 ms	784 KB	Output is correct
21	Correct	2 ms	784 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Correct	1 ms	784 KB	Output is correct
24	Correct	1 ms	784 KB	Output is correct
25	Correct	1 ms	784 KB	Output is correct
26	Correct	1 ms	784 KB	Output is correct
27	Correct	1 ms	784 KB	Output is correct
28	Correct	1 ms	784 KB	Output is correct
29	Correct	1 ms	784 KB	Output is correct
30	Correct	1 ms	784 KB	Output is correct
31	Correct	1 ms	784 KB	Output is correct
32	Correct	1 ms	784 KB	Output is correct
33	Correct	1 ms	784 KB	Output is correct
34	Correct	2 ms	784 KB	Output is correct
35	Correct	1 ms	784 KB	Output is correct
36	Correct	2 ms	784 KB	Output is correct
37	Correct	2 ms	784 KB	Output is correct
38	Correct	2 ms	784 KB	Output is correct
39	Correct	2 ms	784 KB	Output is correct
40	Incorrect	27 ms	784 KB	Output isn't correct
41	Incorrect	42 ms	784 KB	Output isn't correct
42	Incorrect	44 ms	784 KB	Output isn't correct
43	Correct	15 ms	784 KB	Output is correct
44	Incorrect	50 ms	784 KB	Output isn't correct
45	Incorrect	93 ms	784 KB	Output isn't correct
46	Incorrect	54 ms	784 KB	Output isn't correct
47	Incorrect	204 ms	784 KB	Output isn't correct
48	Incorrect	70 ms	784 KB	Output isn't correct
49	Incorrect	10 ms	784 KB	Output isn't correct
50	Incorrect	82 ms	784 KB	Output isn't correct
51	Incorrect	223 ms	784 KB	Output isn't correct
52	Incorrect	71 ms	784 KB	Output isn't correct
53	Incorrect	11 ms	784 KB	Output isn't correct
54	Correct	22 ms	784 KB	Output is correct
55	Incorrect	15 ms	784 KB	Output isn't correct
56	Correct	1 ms	784 KB	Output is correct
57	Correct	2 ms	784 KB	Output is correct
58	Correct	11 ms	784 KB	Output is correct
59	Correct	3 ms	784 KB	Output is correct
60	Correct	7 ms	784 KB	Output is correct
61	Incorrect	13 ms	784 KB	Output isn't correct
62	Correct	2 ms	784 KB	Output is correct
63	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	4 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 ms	1556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	4 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	4 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	5 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	700 KB	Output is correct
2	Correct	3 ms	700 KB	Output is correct
3	Correct	3 ms	720 KB	Output is correct
4	Correct	3 ms	720 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	4 ms	720 KB	Output is correct
7	Correct	1 ms	720 KB	Output is correct
8	Correct	2 ms	720 KB	Output is correct
9	Correct	2 ms	720 KB	Output is correct
10	Correct	3 ms	720 KB	Output is correct
11	Correct	3 ms	720 KB	Output is correct
12	Correct	2 ms	720 KB	Output is correct
13	Correct	2 ms	720 KB	Output is correct
14	Correct	1 ms	720 KB	Output is correct
15	Correct	3 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	784 KB	Output is correct
20	Correct	1 ms	784 KB	Output is correct
21	Correct	2 ms	784 KB	Output is correct
22	Correct	1 ms	784 KB	Output is correct
23	Correct	1 ms	784 KB	Output is correct
24	Correct	1 ms	784 KB	Output is correct
25	Correct	1 ms	784 KB	Output is correct
26	Correct	1 ms	784 KB	Output is correct
27	Correct	1 ms	784 KB	Output is correct
28	Correct	1 ms	784 KB	Output is correct
29	Correct	1 ms	784 KB	Output is correct
30	Correct	1 ms	784 KB	Output is correct
31	Correct	1 ms	784 KB	Output is correct
32	Correct	1 ms	784 KB	Output is correct
33	Correct	1 ms	784 KB	Output is correct
34	Correct	2 ms	784 KB	Output is correct
35	Correct	1 ms	784 KB	Output is correct
36	Correct	2 ms	784 KB	Output is correct
37	Correct	2 ms	784 KB	Output is correct
38	Correct	2 ms	784 KB	Output is correct
39	Correct	2 ms	784 KB	Output is correct
40	Incorrect	27 ms	784 KB	Output isn't correct
41	Incorrect	42 ms	784 KB	Output isn't correct
42	Incorrect	44 ms	784 KB	Output isn't correct
43	Correct	15 ms	784 KB	Output is correct
44	Incorrect	50 ms	784 KB	Output isn't correct
45	Incorrect	93 ms	784 KB	Output isn't correct
46	Incorrect	54 ms	784 KB	Output isn't correct
47	Incorrect	204 ms	784 KB	Output isn't correct
48	Incorrect	70 ms	784 KB	Output isn't correct
49	Incorrect	10 ms	784 KB	Output isn't correct
50	Incorrect	82 ms	784 KB	Output isn't correct
51	Incorrect	223 ms	784 KB	Output isn't correct
52	Incorrect	71 ms	784 KB	Output isn't correct
53	Incorrect	11 ms	784 KB	Output isn't correct
54	Correct	22 ms	784 KB	Output is correct
55	Incorrect	15 ms	784 KB	Output isn't correct
56	Correct	1 ms	784 KB	Output is correct
57	Correct	2 ms	784 KB	Output is correct
58	Correct	11 ms	784 KB	Output is correct
59	Correct	3 ms	784 KB	Output is correct
60	Correct	7 ms	784 KB	Output is correct
61	Incorrect	13 ms	784 KB	Output isn't correct
62	Correct	2 ms	784 KB	Output is correct
63	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	3 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	4 ms	1548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 ms	1556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	4 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	4 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	5 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	7 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	4 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	6 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
93	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
94	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
95	Runtime error	7 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
96	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
97	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
98	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
99	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
100	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
101	Runtime error	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
102	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
103	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
104	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
105	Runtime error	6 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
106	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
107	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #20375

Compilation message

Subtask #1 9.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
9.0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
0 / 25.0

Subtask #4
0 / 26.0

Subtask #5
0 / 27.0