Submission #12786

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

mcg

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int MAX = 200;
const ll INF = 5123456789012345678LL;

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

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

	ll &now = a >= b ? memo[level][0] : memo[level][1];
	maxLevel = max(maxLevel, level);

	if(now != 0) return now;

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

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

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

	return now;
}

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

int main(){
	int t;
	for(scanf("%d", &t); t--;){
		ll a, b;
		scanf("%lld%lld%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: 27 / 27
• Subtask 4: 43 / 43