답안 #20376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20376	2017-02-07T09:56:29 Z		복불복 (OJUZ11_luck)	C++	22 / 100	240 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++){
			ll sum=1;
			for(int j=2,p=i;j<=N;j++){
				while(p>0&&c[j][p]<=c[1][i])p--;
				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	824 KB	Output is correct
3	Correct	3 ms	884 KB	Output is correct
4	Correct	3 ms	884 KB	Output is correct
5	Correct	4 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	2 ms	884 KB	Output is correct
8	Correct	3 ms	884 KB	Output is correct
9	Correct	3 ms	884 KB	Output is correct
10	Correct	3 ms	884 KB	Output is correct
11	Correct	3 ms	884 KB	Output is correct
12	Correct	1 ms	884 KB	Output is correct
13	Correct	2 ms	884 KB	Output is correct
14	Correct	2 ms	884 KB	Output is correct
15	Correct	3 ms	884 KB	Output is correct
16	Correct	2 ms	884 KB	Output is correct
17	Correct	3 ms	884 KB	Output is correct
18	Correct	3 ms	884 KB	Output is correct
19	Correct	2 ms	884 KB	Output is correct
20	Correct	2 ms	884 KB	Output is correct
21	Correct	4 ms	884 KB	Output is correct
22	Correct	2 ms	884 KB	Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	700 KB	Output is correct
2	Correct	3 ms	824 KB	Output is correct
3	Correct	3 ms	884 KB	Output is correct
4	Correct	3 ms	884 KB	Output is correct
5	Correct	4 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	2 ms	884 KB	Output is correct
8	Correct	3 ms	884 KB	Output is correct
9	Correct	3 ms	884 KB	Output is correct
10	Correct	3 ms	884 KB	Output is correct
11	Correct	3 ms	884 KB	Output is correct
12	Correct	1 ms	884 KB	Output is correct
13	Correct	2 ms	884 KB	Output is correct
14	Correct	2 ms	884 KB	Output is correct
15	Correct	3 ms	884 KB	Output is correct
16	Correct	2 ms	884 KB	Output is correct
17	Correct	3 ms	884 KB	Output is correct
18	Correct	3 ms	884 KB	Output is correct
19	Correct	2 ms	884 KB	Output is correct
20	Correct	2 ms	884 KB	Output is correct
21	Correct	4 ms	884 KB	Output is correct
22	Correct	2 ms	884 KB	Output is correct
23	Correct	2 ms	884 KB	Output is correct
24	Correct	2 ms	884 KB	Output is correct
25	Correct	2 ms	884 KB	Output is correct
26	Correct	2 ms	884 KB	Output is correct
27	Correct	2 ms	884 KB	Output is correct
28	Correct	2 ms	884 KB	Output is correct
29	Correct	2 ms	884 KB	Output is correct
30	Correct	1 ms	884 KB	Output is correct
31	Correct	2 ms	884 KB	Output is correct
32	Correct	1 ms	884 KB	Output is correct
33	Correct	2 ms	884 KB	Output is correct
34	Correct	1 ms	884 KB	Output is correct
35	Correct	2 ms	884 KB	Output is correct
36	Correct	2 ms	884 KB	Output is correct
37	Correct	3 ms	884 KB	Output is correct
38	Correct	2 ms	884 KB	Output is correct
39	Correct	2 ms	884 KB	Output is correct
40	Incorrect	24 ms	884 KB	Output isn't correct
41	Incorrect	33 ms	884 KB	Output isn't correct
42	Incorrect	49 ms	884 KB	Output isn't correct
43	Correct	14 ms	884 KB	Output is correct
44	Incorrect	61 ms	884 KB	Output isn't correct
45	Incorrect	83 ms	884 KB	Output isn't correct
46	Incorrect	54 ms	884 KB	Output isn't correct
47	Incorrect	203 ms	884 KB	Output isn't correct
48	Incorrect	70 ms	884 KB	Output isn't correct
49	Incorrect	9 ms	884 KB	Output isn't correct
50	Incorrect	82 ms	884 KB	Output isn't correct
51	Incorrect	240 ms	884 KB	Output isn't correct
52	Incorrect	75 ms	884 KB	Output isn't correct
53	Incorrect	13 ms	884 KB	Output isn't correct
54	Correct	25 ms	884 KB	Output is correct
55	Incorrect	15 ms	884 KB	Output isn't correct
56	Correct	2 ms	884 KB	Output is correct
57	Correct	2 ms	884 KB	Output is correct
58	Correct	11 ms	884 KB	Output is correct
59	Correct	3 ms	884 KB	Output is correct
60	Correct	6 ms	884 KB	Output is correct
61	Incorrect	12 ms	884 KB	Output isn't correct
62	Correct	1 ms	884 KB	Output is correct
63	Runtime error	5 ms	1436 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1540 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	5 ms	1556 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	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	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 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	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	3 ms	1588 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	824 KB	Output is correct
3	Correct	3 ms	884 KB	Output is correct
4	Correct	3 ms	884 KB	Output is correct
5	Correct	4 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	2 ms	884 KB	Output is correct
8	Correct	3 ms	884 KB	Output is correct
9	Correct	3 ms	884 KB	Output is correct
10	Correct	3 ms	884 KB	Output is correct
11	Correct	3 ms	884 KB	Output is correct
12	Correct	1 ms	884 KB	Output is correct
13	Correct	2 ms	884 KB	Output is correct
14	Correct	2 ms	884 KB	Output is correct
15	Correct	3 ms	884 KB	Output is correct
16	Correct	2 ms	884 KB	Output is correct
17	Correct	3 ms	884 KB	Output is correct
18	Correct	3 ms	884 KB	Output is correct
19	Correct	2 ms	884 KB	Output is correct
20	Correct	2 ms	884 KB	Output is correct
21	Correct	4 ms	884 KB	Output is correct
22	Correct	2 ms	884 KB	Output is correct
23	Correct	2 ms	884 KB	Output is correct
24	Correct	2 ms	884 KB	Output is correct
25	Correct	2 ms	884 KB	Output is correct
26	Correct	2 ms	884 KB	Output is correct
27	Correct	2 ms	884 KB	Output is correct
28	Correct	2 ms	884 KB	Output is correct
29	Correct	2 ms	884 KB	Output is correct
30	Correct	1 ms	884 KB	Output is correct
31	Correct	2 ms	884 KB	Output is correct
32	Correct	1 ms	884 KB	Output is correct
33	Correct	2 ms	884 KB	Output is correct
34	Correct	1 ms	884 KB	Output is correct
35	Correct	2 ms	884 KB	Output is correct
36	Correct	2 ms	884 KB	Output is correct
37	Correct	3 ms	884 KB	Output is correct
38	Correct	2 ms	884 KB	Output is correct
39	Correct	2 ms	884 KB	Output is correct
40	Incorrect	24 ms	884 KB	Output isn't correct
41	Incorrect	33 ms	884 KB	Output isn't correct
42	Incorrect	49 ms	884 KB	Output isn't correct
43	Correct	14 ms	884 KB	Output is correct
44	Incorrect	61 ms	884 KB	Output isn't correct
45	Incorrect	83 ms	884 KB	Output isn't correct
46	Incorrect	54 ms	884 KB	Output isn't correct
47	Incorrect	203 ms	884 KB	Output isn't correct
48	Incorrect	70 ms	884 KB	Output isn't correct
49	Incorrect	9 ms	884 KB	Output isn't correct
50	Incorrect	82 ms	884 KB	Output isn't correct
51	Incorrect	240 ms	884 KB	Output isn't correct
52	Incorrect	75 ms	884 KB	Output isn't correct
53	Incorrect	13 ms	884 KB	Output isn't correct
54	Correct	25 ms	884 KB	Output is correct
55	Incorrect	15 ms	884 KB	Output isn't correct
56	Correct	2 ms	884 KB	Output is correct
57	Correct	2 ms	884 KB	Output is correct
58	Correct	11 ms	884 KB	Output is correct
59	Correct	3 ms	884 KB	Output is correct
60	Correct	6 ms	884 KB	Output is correct
61	Incorrect	12 ms	884 KB	Output isn't correct
62	Correct	1 ms	884 KB	Output is correct
63	Runtime error	5 ms	1436 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	3 ms	1540 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	5 ms	1556 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	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	3 ms	1576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	3 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	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	3 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	6 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	5 ms	1588 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	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	3 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	5 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	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
96	Runtime error	4 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	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
100	Runtime error	4 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
101	Runtime error	9 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
102	Runtime error	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
103	Runtime error	5 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	5 ms	1588 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
106	Runtime error	5 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)

답안 #20376

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