Submission #12072

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

mcg

#include<stdio.h>
#include<algorithm>
#define INF 999999999999999999LL
using namespace std;
long long a, b, sub, mod, C1, C2, TC1, TC2;
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 + (b / a)* sub);
				TC2 = min(C2 + (b / a)*sub, TC1 + mod);
				b = b%a;
			}
			else{
				if (C1 > C2 + mod)C1 = C2 + mod;
				TC2 = min(C1 + mod, C2 + (a / b)* sub); 
				TC1 = min(C1 + (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: 0 / 27
• Subtask 4: 0 / 43