Submission #427274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427274	2021-06-14T13:53:20 Z	model_code	GCD-sum (CPSPC17_gcds)	C++17	10 / 100	805 ms	5944 KB

Main

# include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
	if (a == 0)
		return b;
	else
		return gcd(b % a, a);
}
const int MN = 20;
long long gcd_arr[1 << MN];
long long a[MN];
const long long inf = 1e18 + 44;
long long dp[1 << MN][MN + 1];
int main() {
	int n;
	scanf("%d", &n);
	assert(n <= MN);
	for (int i = 0; i < n; ++i)
		scanf("%lld", a + i);
	gcd_arr[0] = 0;
	for (int mask = 1; mask < (1 << n); ++mask) {
		int i = __builtin_ctz(mask);
		assert((1 << i) == (mask & -mask));
		gcd_arr[mask] = gcd(a[i], gcd_arr[mask &~ (1 << i)]);
	}
	for (int mask = 0; mask < (1 << n); ++mask)
		for (int i = 0; i <= n; ++i)
			dp[mask][i] = -inf;
	dp[0][0] = 0;
	for (int mask = 1; mask < (1 << n); ++mask)
		for (int i = 1; i <= n; ++i) {
			assert(dp[mask][i] == -inf);
			for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
				assert(subset > 0);
				dp[mask][i] = max(dp[mask][i], dp[mask &~ subset][i - 1] + gcd_arr[subset]);
			}
		}
	for (int mask = 1; mask < (1 << n); ++mask)
		assert(dp[mask][1] == gcd_arr[mask]);
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", dp[(1 << n) - 1][i]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%lld", a + i);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	690 ms	5932 KB	Output is correct
17	Correct	720 ms	5936 KB	Output is correct
18	Correct	747 ms	5940 KB	Output is correct
19	Correct	773 ms	5928 KB	Output is correct
20	Correct	692 ms	5928 KB	Output is correct
21	Correct	681 ms	5836 KB	Output is correct
22	Correct	750 ms	5936 KB	Output is correct
23	Correct	723 ms	5932 KB	Output is correct
24	Correct	805 ms	5932 KB	Output is correct
25	Correct	726 ms	5944 KB	Output is correct
26	Correct	672 ms	5932 KB	Output is correct
27	Correct	700 ms	5932 KB	Output is correct
28	Correct	738 ms	5932 KB	Output is correct
29	Correct	679 ms	5932 KB	Output is correct
30	Correct	691 ms	5932 KB	Output is correct

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	460 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	388 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	690 ms	5932 KB	Output is correct
17	Correct	720 ms	5936 KB	Output is correct
18	Correct	747 ms	5940 KB	Output is correct
19	Correct	773 ms	5928 KB	Output is correct
20	Correct	692 ms	5928 KB	Output is correct
21	Correct	681 ms	5836 KB	Output is correct
22	Correct	750 ms	5936 KB	Output is correct
23	Correct	723 ms	5932 KB	Output is correct
24	Correct	805 ms	5932 KB	Output is correct
25	Correct	726 ms	5944 KB	Output is correct
26	Correct	672 ms	5932 KB	Output is correct
27	Correct	700 ms	5932 KB	Output is correct
28	Correct	738 ms	5932 KB	Output is correct
29	Correct	679 ms	5932 KB	Output is correct
30	Correct	691 ms	5932 KB	Output is correct
31	Runtime error	9 ms	460 KB	Execution killed with signal 6
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	388 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	690 ms	5932 KB	Output is correct
17	Correct	720 ms	5936 KB	Output is correct
18	Correct	747 ms	5940 KB	Output is correct
19	Correct	773 ms	5928 KB	Output is correct
20	Correct	692 ms	5928 KB	Output is correct
21	Correct	681 ms	5836 KB	Output is correct
22	Correct	750 ms	5936 KB	Output is correct
23	Correct	723 ms	5932 KB	Output is correct
24	Correct	805 ms	5932 KB	Output is correct
25	Correct	726 ms	5944 KB	Output is correct
26	Correct	672 ms	5932 KB	Output is correct
27	Correct	700 ms	5932 KB	Output is correct
28	Correct	738 ms	5932 KB	Output is correct
29	Correct	679 ms	5932 KB	Output is correct
30	Correct	691 ms	5932 KB	Output is correct
31	Runtime error	9 ms	460 KB	Execution killed with signal 6
32	Halted	0 ms	0 KB	-

Submission #427274

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 8.0

Subtask #4 0 / 8.0

Subtask #5 0 / 14.0

Subtask #6 0 / 25.0

Subtask #7 0 / 35.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 8.0

Subtask #4
0 / 8.0

Subtask #5
0 / 14.0

Subtask #6
0 / 25.0

Subtask #7
0 / 35.0