답안 #20134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20134	2016-02-27T15:36:29 Z	hongjun7	Min-cost GCD (GA9_mcg)	C++14	30 / 100	1000 ms	1720 KB

mcg

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, p, q;
map <pair<ll, ll>, ll> d;
ll f(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
	if (d.count({ x, y })) return d[{x, y}];
	ll d1 = f(y, x%y) + p;
	ll d2 = 0;
	if (x >= y) d2 = f(x % y, y) + (x / y)*q;
	else d2 = f(x, y % x) + (y / x)*q;
	ll D = min(d1, d2);
	d[{x, y}] = D;
	return D;
}
int main() {
	int T;
	for (cin >> T; T--; ) {
		cin >> a >> b >> p >> q;
		d.clear();
		cout << f(a, b) << "\n";
	}
}

Subtask #1

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1720 KB	Output is correct
2	Correct	0 ms	1720 KB	Output is correct
3	Correct	0 ms	1720 KB	Output is correct
4	Correct	0 ms	1720 KB	Output is correct
5	Correct	0 ms	1720 KB	Output is correct
6	Correct	0 ms	1720 KB	Output is correct
7	Correct	0 ms	1720 KB	Output is correct
8	Correct	0 ms	1720 KB	Output is correct
9	Correct	0 ms	1720 KB	Output is correct
10	Correct	0 ms	1720 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	437 ms	1720 KB	Output is correct
2	Correct	554 ms	1720 KB	Output is correct
3	Correct	472 ms	1720 KB	Output is correct
4	Correct	493 ms	1720 KB	Output is correct
5	Correct	442 ms	1720 KB	Output is correct
6	Correct	491 ms	1720 KB	Output is correct
7	Correct	501 ms	1720 KB	Output is correct
8	Correct	439 ms	1720 KB	Output is correct
9	Correct	485 ms	1720 KB	Output is correct
10	Correct	463 ms	1720 KB	Output is correct
11	Correct	533 ms	1720 KB	Output is correct
12	Correct	442 ms	1720 KB	Output is correct
13	Correct	459 ms	1720 KB	Output is correct
14	Correct	22 ms	1720 KB	Output is correct
15	Correct	0 ms	1720 KB	Output is correct
16	Correct	0 ms	1720 KB	Output is correct
17	Correct	0 ms	1720 KB	Output is correct

Subtask #3

0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1720 KB	Output is correct
2	Incorrect	7 ms	1720 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1000 ms	1720 KB	Program timed out
2	Halted	0 ms	0 KB	-