Submission #12074

#	Time	Username	Problem	Language	Result	Execution time	Memory
12074		ainta	Min-cost GCD (GA9_mcg)	C++98	100 / 100	284 ms	1084 KiB

mcg

#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));
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43