oj.uz

답안 #12246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12246 2014-12-25T19:30:23 Z pro0331 Min-cost GCD (GA9_mcg) C++
14 / 100
 1000 ms 32768 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 552 ms 32768 KB Memory limit exceeded
2 Halted 0 ms 0 KB -