oj.uz

답안 #20133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20133 2016-02-27T15:34:39 Z hongjun7 Min-cost GCD (GA9_mcg) C++14
14 / 100
 1000 ms 32768 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) + q;
	else d2 = f(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";
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1856 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 3208 KB Output is correct
2 Correct 86 ms 4812 KB Output is correct
3 Correct 122 ms 3032 KB Output is correct
4 Correct 114 ms 4988 KB Output is correct
5 Correct 245 ms 9756 KB Output is correct
6 Correct 101 ms 4412 KB Output is correct
7 Correct 114 ms 4396 KB Output is correct
8 Correct 101 ms 6984 KB Output is correct
9 Correct 153 ms 10124 KB Output is correct
10 Correct 86 ms 2620 KB Output is correct
11 Correct 82 ms 2788 KB Output is correct
12 Correct 126 ms 5360 KB Output is correct
13 Correct 175 ms 15900 KB Output is correct
14 Memory limit exceeded 18 ms 32768 KB Memory limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

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