답안 #20134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20134 2016-02-27T15:36:29 Z hongjun7 Min-cost GCD (GA9_mcg) C++14
30 / 100
1000 ms 1720 KB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, p, q;
map <pair<ll, ll>, ll> d;
ll f(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
	if (d.count({ x, y })) return d[{x, y}];
	ll d1 = f(y, x%y) + p;
	ll d2 = 0;
	if (x >= y) d2 = f(x % y, y) + (x / y)*q;
	else d2 = f(x, y % x) + (y / x)*q;
	ll D = min(d1, d2);
	d[{x, y}] = D;
	return D;
}
int main() {
	int T;
	for (cin >> T; T--; ) {
		cin >> a >> b >> p >> q;
		d.clear();
		cout << f(a, b) << "\n";
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Correct 0 ms 1720 KB Output is correct
3 Correct 0 ms 1720 KB Output is correct
4 Correct 0 ms 1720 KB Output is correct
5 Correct 0 ms 1720 KB Output is correct
6 Correct 0 ms 1720 KB Output is correct
7 Correct 0 ms 1720 KB Output is correct
8 Correct 0 ms 1720 KB Output is correct
9 Correct 0 ms 1720 KB Output is correct
10 Correct 0 ms 1720 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 437 ms 1720 KB Output is correct
2 Correct 554 ms 1720 KB Output is correct
3 Correct 472 ms 1720 KB Output is correct
4 Correct 493 ms 1720 KB Output is correct
5 Correct 442 ms 1720 KB Output is correct
6 Correct 491 ms 1720 KB Output is correct
7 Correct 501 ms 1720 KB Output is correct
8 Correct 439 ms 1720 KB Output is correct
9 Correct 485 ms 1720 KB Output is correct
10 Correct 463 ms 1720 KB Output is correct
11 Correct 533 ms 1720 KB Output is correct
12 Correct 442 ms 1720 KB Output is correct
13 Correct 459 ms 1720 KB Output is correct
14 Correct 22 ms 1720 KB Output is correct
15 Correct 0 ms 1720 KB Output is correct
16 Correct 0 ms 1720 KB Output is correct
17 Correct 0 ms 1720 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Incorrect 7 ms 1720 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1720 KB Program timed out
2 Halted 0 ms 0 KB -