Submission #12246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
12246	2014-12-25T19:30:23 Z	pro0331	Min-cost GCD (GA9_mcg)	C++	14 / 100	1000 ms	32768 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	1 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct

Subtask #2

0.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	1404 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	2984 KB	Output is correct
2	Correct	95 ms	4864 KB	Output is correct
3	Correct	83 ms	2792 KB	Output is correct
4	Correct	90 ms	5052 KB	Output is correct
5	Correct	198 ms	10624 KB	Output is correct
6	Correct	97 ms	4384 KB	Output is correct
7	Correct	89 ms	4372 KB	Output is correct
8	Correct	99 ms	7388 KB	Output is correct
9	Correct	141 ms	11040 KB	Output is correct
10	Correct	75 ms	2292 KB	Output is correct
11	Correct	71 ms	2484 KB	Output is correct
12	Correct	100 ms	5484 KB	Output is correct
13	Correct	143 ms	17788 KB	Output is correct
14	Memory limit exceeded	14 ms	32768 KB	Memory limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	552 ms	32768 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-