답안 #12780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12780	2015-01-03T12:51:33 Z	Qwaz	Min-cost GCD (GA9_mcg)	C++	30 / 100	475 ms	1084 KB

mcg

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int MAX = 70;

ll p, q, memo[MAX][2];

ll minGcd(int a, int b, int level){
	if(a == 0 || b == 0) return 0;

	ll &now = a >= b ? memo[level][0] : memo[level][1];

	if(now != 0) return now;

	if(a >= b){
		now = minGcd(b, a%b, level+1)+p;

		int count = (a - (a%b))/b;
		now = min(now, minGcd(a%b, b, level+1) + q*count);
	} else {
		now = minGcd(b, a, level)+p;

		int count = (b - (b%a))/a;
		now = min(now, minGcd(a, b%a, level+1) + q*count);
	}

	return now;
}

void reset(){
	for(int i = 0; i < MAX; i++)
		memo[i][0] = memo[i][1] = 0;
}

int main(){
	int t;
	for(scanf("%d", &t); t--;){
		int a, b;
		scanf("%d%d%lld%lld", &a, &b, &p, &q);

		printf("%lld\n", minGcd(a, b, 0));

		reset();
	}

	return 0;
}

Subtask #1

14.0 / 14.0

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

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	1084 KB	Output is correct
2	Correct	100 ms	1084 KB	Output is correct
3	Correct	99 ms	1084 KB	Output is correct
4	Correct	95 ms	1084 KB	Output is correct
5	Correct	87 ms	1084 KB	Output is correct
6	Correct	98 ms	1084 KB	Output is correct
7	Correct	99 ms	1084 KB	Output is correct
8	Correct	88 ms	1084 KB	Output is correct
9	Correct	91 ms	1084 KB	Output is correct
10	Correct	93 ms	1084 KB	Output is correct
11	Correct	101 ms	1084 KB	Output is correct
12	Correct	94 ms	1084 KB	Output is correct
13	Correct	97 ms	1084 KB	Output is correct
14	Correct	1 ms	1084 KB	Output is correct
15	Correct	0 ms	1084 KB	Output is correct
16	Correct	0 ms	1084 KB	Output is correct
17	Correct	0 ms	1084 KB	Output is correct

Subtask #3

0.0 / 27.0

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

Subtask #4

0.0 / 43.0

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