답안 #12121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12121	2014-12-21T07:27:02 Z	kriii	Min-cost GCD (GA9_mcg)	C++14	41 / 100	110 ms	32768 KB

mcg

#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;

long long a,b,p,q,l;
int t;
std::map<int, long long> chk[100000];

long long go(long long a, long long b)
{
	if (a == 0 || b == 0) return 0;
	if (a == b) return p < q ? p : q;
	unsigned int h = a*b+a*3+b;
	long long &r = chk[t][h];
	if (r) return r;
	r = p + go(b,a%b);
	if (a > b){
		long long d = a / b, e = q * d;
		if (d <= l) r = min(r, e+go(a-b*d,b));
	}
	else{
		long long d = b / a, e = q * d;
		if (d <= l) r = min(r, e+go(a,b-a*d));
	}
	return r;
}

int main()
{
	int T; scanf ("%d",&T); while (T--){
		scanf ("%lld %lld %lld %lld",&a,&b,&p,&q);
		l = 1e18 / q;
		printf ("%lld\n",go(a,b));
		t++;
	}

	return 0;
}

Subtask #1

14.0 / 14.0

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

Subtask #2

0.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Memory limit exceeded	70 ms	32768 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	7880 KB	Output is correct
2	Correct	0 ms	7880 KB	Output is correct
3	Correct	7 ms	7880 KB	Output is correct
4	Correct	11 ms	7880 KB	Output is correct
5	Correct	11 ms	7880 KB	Output is correct
6	Correct	12 ms	7880 KB	Output is correct
7	Correct	7 ms	7880 KB	Output is correct
8	Correct	11 ms	7880 KB	Output is correct
9	Correct	11 ms	7880 KB	Output is correct
10	Correct	12 ms	7880 KB	Output is correct
11	Correct	4 ms	7880 KB	Output is correct
12	Correct	7 ms	7880 KB	Output is correct
13	Correct	7 ms	7880 KB	Output is correct
14	Correct	4 ms	6428 KB	Output is correct
15	Correct	5 ms	6560 KB	Output is correct
16	Correct	3 ms	6560 KB	Output is correct
17	Correct	2 ms	6560 KB	Output is correct
18	Correct	3 ms	6560 KB	Output is correct
19	Correct	11 ms	8540 KB	Output is correct
20	Correct	10 ms	8540 KB	Output is correct
21	Correct	6 ms	8408 KB	Output is correct
22	Correct	9 ms	8540 KB	Output is correct
23	Correct	8 ms	8408 KB	Output is correct
24	Correct	4 ms	8408 KB	Output is correct
25	Correct	9 ms	8540 KB	Output is correct
26	Correct	10 ms	8408 KB	Output is correct
27	Correct	12 ms	8408 KB	Output is correct
28	Correct	9 ms	8540 KB	Output is correct
29	Correct	8 ms	8540 KB	Output is correct
30	Correct	14 ms	8408 KB	Output is correct
31	Correct	4 ms	8540 KB	Output is correct

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Memory limit exceeded	110 ms	32768 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-