답안 #12074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12074 2014-12-20T21:17:03 Z ainta Min-cost GCD (GA9_mcg) C++
100 / 100
284 ms 1084 KB
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#define INF 999999999999999999LL
using namespace std;
long long a, b, sub, mod, C1, C2, TC1, TC2;
long long Mul(long long a, long long b){
	if (a && INF / a < b)return INF;
	return a*b;
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--){
		scanf("%lld%lld", &a, &b);
		scanf("%lld%lld", &mod, &sub);
		C1 = 0, C2 = INF;
		while (a && b){
			if (a == b){
				C1 = C1 + min(sub, mod);
				C2 = C2 + min(sub, mod);
				a -= b;
				continue;
			}
			if (a < b){
				if (C2 > C1 + mod)C2 = C1 + mod;
				TC1 = min(C2 + mod, C1 + Mul(b / a, sub));
				TC2 = min(C2 + Mul(b / a,sub), TC1 + mod);
				b = b%a;
			}
			else{
				if (C1 > C2 + mod)C1 = C2 + mod;
				TC2 = min(C1 + mod, C2 + Mul(a / b, sub));
				TC1 = min(C1 + Mul(a / b,sub), TC2 + mod);
				a = a%b;
			}
			C1 = TC1, C2 = TC2;
		}
		printf("%lld\n", min(C1, C2));
	}
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 1084 KB Output is correct
2 Correct 90 ms 1084 KB Output is correct
3 Correct 91 ms 1084 KB Output is correct
4 Correct 91 ms 1084 KB Output is correct
5 Correct 91 ms 1084 KB Output is correct
6 Correct 89 ms 1084 KB Output is correct
7 Correct 66 ms 1084 KB Output is correct
8 Correct 57 ms 1084 KB Output is correct
9 Correct 73 ms 1084 KB Output is correct
10 Correct 77 ms 1084 KB Output is correct
11 Correct 94 ms 1084 KB Output is correct
12 Correct 76 ms 1084 KB Output is correct
13 Correct 91 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 1 ms 1084 KB Output is correct
17 Correct 1 ms 1084 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1084 KB Output is correct
2 Correct 1 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 2 ms 1084 KB Output is correct
7 Correct 1 ms 1084 KB Output is correct
8 Correct 1 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct
11 Correct 1 ms 1084 KB Output is correct
12 Correct 0 ms 1084 KB Output is correct
13 Correct 2 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
18 Correct 0 ms 1084 KB Output is correct
19 Correct 0 ms 1084 KB Output is correct
20 Correct 2 ms 1084 KB Output is correct
21 Correct 0 ms 1084 KB Output is correct
22 Correct 1 ms 1084 KB Output is correct
23 Correct 1 ms 1084 KB Output is correct
24 Correct 0 ms 1084 KB Output is correct
25 Correct 0 ms 1084 KB Output is correct
26 Correct 1 ms 1084 KB Output is correct
27 Correct 0 ms 1084 KB Output is correct
28 Correct 0 ms 1084 KB Output is correct
29 Correct 0 ms 1084 KB Output is correct
30 Correct 0 ms 1084 KB Output is correct
31 Correct 0 ms 1084 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 1084 KB Output is correct
2 Correct 201 ms 1084 KB Output is correct
3 Correct 245 ms 1084 KB Output is correct
4 Correct 246 ms 1084 KB Output is correct
5 Correct 249 ms 1084 KB Output is correct
6 Correct 252 ms 1084 KB Output is correct
7 Correct 234 ms 1084 KB Output is correct
8 Correct 235 ms 1084 KB Output is correct
9 Correct 238 ms 1084 KB Output is correct
10 Correct 247 ms 1084 KB Output is correct
11 Correct 229 ms 1084 KB Output is correct
12 Correct 248 ms 1084 KB Output is correct
13 Correct 248 ms 1084 KB Output is correct
14 Correct 274 ms 1084 KB Output is correct
15 Correct 273 ms 1084 KB Output is correct
16 Correct 271 ms 1084 KB Output is correct
17 Correct 255 ms 1084 KB Output is correct
18 Correct 252 ms 1084 KB Output is correct
19 Correct 130 ms 1084 KB Output is correct
20 Correct 126 ms 1084 KB Output is correct
21 Correct 119 ms 1084 KB Output is correct
22 Correct 131 ms 1084 KB Output is correct
23 Correct 129 ms 1084 KB Output is correct
24 Correct 157 ms 1084 KB Output is correct
25 Correct 130 ms 1084 KB Output is correct
26 Correct 144 ms 1084 KB Output is correct
27 Correct 148 ms 1084 KB Output is correct
28 Correct 284 ms 1084 KB Output is correct
29 Correct 253 ms 1084 KB Output is correct
30 Correct 258 ms 1084 KB Output is correct
31 Correct 239 ms 1084 KB Output is correct
32 Correct 261 ms 1084 KB Output is correct
33 Correct 273 ms 1084 KB Output is correct
34 Correct 262 ms 1084 KB Output is correct
35 Correct 273 ms 1084 KB Output is correct