Submission #12159

#	Time	Username	Problem	Language	Result	Execution time	Memory
12159		xhae	Min-cost GCD (GA9_mcg)	C++14	41 / 100	1000 ms	1528 KiB

mcg

#include <set>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

long long dp[200][200];

long long a, b, p, q;
const long long INF = 1000000ll * 1000000ll * 500000ll;

set<long long> nodes;
map<long long, int> hash_;

void preproc(long long a, long long b)
{
	nodes.insert(a);
	nodes.insert(b);
	if(a == 0 || b == 0) return;
	preproc(b, a % b);
}

long long getAns(long long a, long long b)
{
	if(a == 0 || b == 0) return 0;

	int i1 = hash_[a], i2 = hash_[b];
	long long &ret = dp[i1][i2];
	if(ret != -1) return ret;
	
	ret = p + getAns(b, a % b);

	if(a >= b)
	{
		long long howMany = a / b;
		if(howMany <= ret / (double)q)
		{
			long long cand = howMany * q + getAns(a % b, b);
			ret = min(cand, ret);
		}
	}
	else
	{
		long long howMany = b / a;
		if(howMany <= ret / (double)q)
		{
			long long cand = howMany * q + getAns(a, b % a);
			ret = min(cand, ret);
		}
	}

	return ret;
}

int main(void)
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
		nodes.clear();
		preproc(a, b);
		int ind = 0;
		hash_.clear();
		for(auto v: nodes) hash_[v] = ind++;

		memset(dp, -1, sizeof(dp));
		printf("%lld\n", getAns(a, b));
	}

	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 16
• Subtask 3: 27 / 27
• Subtask 4: 0 / 43