Submission #12246

#	Time	Username	Problem	Language	Result	Execution time	Memory
12246		pro0331	Min-cost GCD (GA9_mcg)	C++98	14 / 100	1000 ms	32768 KiB

mcg

#include <stdio.h>
#include <map>

struct pair {
	long long x;
	long long y;
	bool operator <(const pair&a) const {return ((x < a.x) || (x == a.x && y < a.y));}
};

std::map<pair, long long> cache;

void do_sh(pair &in, pair &out)
{
	out.x = in.y;
	out.y = in.x % in.y;
}

void do_ss(pair &in, pair &out)
{
	if (in.x >= in.y) {
		out.x = in.x - in.y;
		out.y = in.y;
	} else {
		out.x = in.x;
		out.y = in.y - in.x;
	}
}

long long cost(pair &x, long long p, long long q)
{
	if (x.x == 0 || x.y == 0)
		return 0LL;
	std::map<pair, long long>::iterator it = cache.find(x);
	if (it != cache.end())
		return it->second;
	
	long long cost_sh, cost_ss;
	pair t;

	do_sh(x, t);
	cost_sh = p + cost(t, p, q);
	do_ss(x, t);
	cost_ss = q + cost(t, p, q);

	long long ret = (cost_sh < cost_ss)? cost_sh : cost_ss;
	cache[x] = ret;
	return ret;
}


int main()
{
	int T;
	pair i;
	long long p, q;
	for (scanf("%d", &T); T; T--) {
		cache.clear();
		scanf("%lld%lld%lld%lld", &i.x, &i.y, &p, &q);
		printf("%llu\n", cost(i, p, q));
	}
}

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