oj.uz

답안 #12781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12781 2015-01-03T12:53:01 Z Qwaz Min-cost GCD (GA9_mcg) C++
30 / 100
 386 ms 1084 KB 
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int MAX = 70;

ll p, q, memo[MAX][2];

ll minGcd(ll a, ll b, int level){
	if(a == 0 || b == 0) return 0;

	ll &now = a >= b ? memo[level][0] : memo[level][1];

	if(now != 0) return now;

	if(a >= b){
		now = minGcd(b, a%b, level+1)+p;

		int count = (a - (a%b))/b;
		now = min(now, minGcd(a%b, b, level+1) + q*count);
	} else {
		now = minGcd(b, a, level)+p;

		int count = (b - (b%a))/a;
		now = min(now, minGcd(a, b%a, level+1) + q*count);
	}

	return now;
}

void reset(){
	for(int i = 0; i < MAX; i++)
		memo[i][0] = memo[i][1] = 0;
}

int main(){
	int t;
	for(scanf("%d", &t); t--;){
		ll a, b;
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);

		printf("%lld\n", minGcd(a, b, 0));

		reset();
	}

	return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 0 ms 1084 KB Output is correct
6 Correct 0 ms 1084 KB Output is correct
7 Correct 0 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 1084 KB Output is correct
2 Correct 124 ms 1084 KB Output is correct
3 Correct 127 ms 1084 KB Output is correct
4 Correct 110 ms 1084 KB Output is correct
5 Correct 107 ms 1084 KB Output is correct
6 Correct 116 ms 1084 KB Output is correct
7 Correct 109 ms 1084 KB Output is correct
8 Correct 102 ms 1084 KB Output is correct
9 Correct 123 ms 1084 KB Output is correct
10 Correct 110 ms 1084 KB Output is correct
11 Correct 121 ms 1084 KB Output is correct
12 Correct 109 ms 1084 KB Output is correct
13 Correct 120 ms 1084 KB Output is correct
14 Correct 0 ms 1084 KB Output is correct
15 Correct 0 ms 1084 KB Output is correct
16 Correct 0 ms 1084 KB Output is correct
17 Correct 1 ms 1084 KB Output is correct

Subtask #3
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Incorrect 2 ms 1084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 386 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -