Submission #429514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
429514	2021-06-16T05:01:51 Z	최서현(#7502)	GCD-sum (CPSPC17_gcds)	C++17	5 / 100	2000 ms	312 KB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> A(n); for(int i = 0; i < n; ++i) cin >> A[i];
    long long ans[n];
    for(int cs = n; cs >= 1; --cs)
    {
        long long sum = 0;
        for(auto i : A) sum += i;
        ans[cs - 1] = sum;

        int mn = sum; pii id;
        for(int i = 0; i < (int)A.size(); ++i)
        {
            for(int j = i + 1; j < (int)A.size(); ++j)
            {
                int t = A[i] + A[j] - __gcd(A[i], A[j]);
                if(mn > t) mn = t, id = {i, j};
            }
        }

        vector<int> B;
        for(int i = 0; i < (int)A.size(); ++i)
            if(i != id.ff && i != id.ss) B.push_back(A[i]);
        B.push_back(__gcd(A[id.ff], A[id.ss]));
        A = B;
    }

    for(int i = 0; i < n; ++i) cout << ans[i] << '\n';
}

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	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	312 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	1 ms	204 KB	Output is correct
6	Correct	1 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	312 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	1 ms	308 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	204 KB	Output is correct
2	Correct	7 ms	204 KB	Output is correct
3	Correct	7 ms	204 KB	Output is correct
4	Incorrect	5 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	2067 ms	312 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	1 ms	204 KB	Output is correct
6	Correct	1 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	312 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	1 ms	308 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	2067 ms	312 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	1 ms	204 KB	Output is correct
6	Correct	1 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	312 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	1 ms	308 KB	Output is correct
21	Incorrect	1 ms	204 KB	Output isn't correct
22	Halted	0 ms	0 KB	-