Submission #12247

#	Time	Username	Problem	Language	Result	Execution time	Memory
12247		pro0331	Min-cost GCD (GA9_mcg)	C++98	30 / 100	1000 ms	1212 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;
long long limit;

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, long long cur_cost)
{
	if (x.x == 0 || x.y == 0)
		return cur_cost;

	std::map<pair, long long>::iterator it = cache.find(x);
	long long ret;
	long long cost_sh = 0, cost_ss = 0;
	pair t;

	if (it != cache.end()) {
		ret = it->second + cur_cost;
		goto RET;
	}

	if (cur_cost + p <= limit) {
		do_sh(x, t);
		cost_sh = cost(t, p, q, cur_cost + p);
	}
	if (cur_cost + q <= limit) {
		do_ss(x, t);
		cost_ss = cost(t, p, q, cur_cost + q);
	}

	if (cost_sh && cost_ss) {
		ret = (cost_sh < cost_ss)? cost_sh : cost_ss;
		cache[x] = ret - cur_cost;
	} else if (cost_sh) {
		ret = cost_sh;
	} else if (cost_ss) {
		ret = cost_ss;
	} else {
		return 0;
	}
	
RET:
	if (ret <= limit) {
		limit = ret;
		return ret;
	} else {
		return 0;
	}
}

long long check_limit(pair &x, long long p)
{
	limit = 0;
	pair i1, i2;
	for (i1 = x; i1.x && i1.y; limit += p) {
		do_sh(i1, i2);
		i1 = i2;
	}
}


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);
		check_limit(i, p);
		printf("%llu\n", cost(i, p, q, 0));
	}
}

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