Submission #429556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
429556	2021-06-16T06:36:45 Z	송준혁(#7525)	GCD-sum (CPSPC17_gcds)	C++17	5 / 100	2000 ms	300 KB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N;
LL A[505050], S;
LL ans[505050];

LL GCD(LL x, LL y){
	if (!y) return x;
	return GCD(y, x%y);
}

int main(){
	LL x;
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%lld", &A[i]), S+=A[i];
	ans[N] = S;
	for (int k=N; k>1; k--){
		int a=0, b=0;
		LL mn = INF;
		for (int i=1; i<=k; i++) for (int j=i+1; j<=k; j++){
			if (mn > A[i]+A[j]-GCD(A[i], A[j])){
				mn = A[i]+A[j]-GCD(A[i], A[j]);
				a = i, b = j;
			}
		}
		swap(A[b], A[k]);
		A[a] = GCD(A[a], A[k]);
		S -= mn;
		ans[k-1] = S;
	}
	for (int i=1; i<=N; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:22:5: warning: unused variable 'x' [-Wunused-variable]
   22 |  LL x;
      |     ^
Main.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:24:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  for (int i=1; i<=N; i++) scanf("%lld", &A[i]), S+=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	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 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	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct

Subtask #2

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	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 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	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Incorrect	1 ms	204 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	300 KB	Output is correct
2	Correct	8 ms	300 KB	Output is correct
3	Correct	7 ms	204 KB	Output is correct
4	Incorrect	6 ms	204 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2062 ms	204 KB	Time limit exceeded
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	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 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	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Incorrect	1 ms	204 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #6

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2062 ms	204 KB	Time limit exceeded
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	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 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	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Incorrect	1 ms	204 KB	Output isn't correct
22	Halted	0 ms	0 KB	-