답안 #20135

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

mcg

#include <cstdio>
#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, d2 = 1e18;
	if (x >= y) {
		if ((x / y)*q < d1) d2 = f(x % y, y) + (x / y)*q;
	}
	else {
		if ((y / x)*q < d1) d2 = f(x, y % x) + (y / x)*q;
	}
	if (d1 > d2) d1 = d2;
	d[{x, y}] = d1;
	return d1;
}
int main() {
	int T;
	for (scanf("%d", &T); T--; ) {
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
		d.clear();
		printf("%lld\n", f(a, b));
	}
}

Subtask #1

14.0 / 14.0

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

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	1212 KB	Output is correct
2	Correct	191 ms	1212 KB	Output is correct
3	Correct	178 ms	1212 KB	Output is correct
4	Correct	205 ms	1212 KB	Output is correct
5	Correct	127 ms	1212 KB	Output is correct
6	Correct	198 ms	1212 KB	Output is correct
7	Correct	192 ms	1212 KB	Output is correct
8	Correct	144 ms	1212 KB	Output is correct
9	Correct	180 ms	1212 KB	Output is correct
10	Correct	145 ms	1212 KB	Output is correct
11	Correct	174 ms	1212 KB	Output is correct
12	Correct	118 ms	1212 KB	Output is correct
13	Correct	167 ms	1212 KB	Output is correct
14	Correct	0 ms	1212 KB	Output is correct
15	Correct	1 ms	1212 KB	Output is correct
16	Correct	3 ms	1212 KB	Output is correct
17	Correct	0 ms	1212 KB	Output is correct

Subtask #3

0.0 / 27.0

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

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	847 ms	1212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-