Submission #20133

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20133	2016-02-27T15:34:39 Z	hongjun7	Min-cost GCD (GA9_mcg)	C++14	14 / 100	1000 ms	32768 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) + q;
	else d2 = f(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

#	Verdict	Execution time	Memory	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

0.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	1856 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	3208 KB	Output is correct
2	Correct	86 ms	4812 KB	Output is correct
3	Correct	122 ms	3032 KB	Output is correct
4	Correct	114 ms	4988 KB	Output is correct
5	Correct	245 ms	9756 KB	Output is correct
6	Correct	101 ms	4412 KB	Output is correct
7	Correct	114 ms	4396 KB	Output is correct
8	Correct	101 ms	6984 KB	Output is correct
9	Correct	153 ms	10124 KB	Output is correct
10	Correct	86 ms	2620 KB	Output is correct
11	Correct	82 ms	2788 KB	Output is correct
12	Correct	126 ms	5360 KB	Output is correct
13	Correct	175 ms	15900 KB	Output is correct
14	Memory limit exceeded	18 ms	32768 KB	Memory limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	662 ms	32768 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-