Submission #12157

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

mcg

#include <map>
#include <cstdio>
#include <algorithm>

using namespace std;

map<pair<long long, long long>, long long> dp;

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

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

	pair<long long, long long> cur = make_pair(a, b);
	if(dp.count(cur)) return dp[cur];
	
	long long 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 dp[cur] = ret;
}

int main(void)
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
		dp.clear();
		printf("%lld\n", getAns(a, b));
	}

	return 0;
}

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