Submission #12780

#	Time	Username	Problem	Language	Result	Execution time	Memory
12780		Qwaz	Min-cost GCD (GA9_mcg)	C++98	30 / 100	475 ms	1084 KiB

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 / 14
• Subtask 2: 16 / 16
• Subtask 3: 0 / 27
• Subtask 4: 0 / 43