Submission #12172

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

mcg

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long lld;

lld a, b, p, q, dy[55][2];

void gcd(lld ix, lld x, lld y){
	if(x<y)swap(x,y);
	if(y==0){
		dy[ix][0]=dy[ix][1]=0;
		return;
	}
	gcd(ix+1, y, x%y);
	dy[ix][0]=min(p+dy[ix+1][0], q*(x/y)+dy[ix+1][1]);
	dy[ix][1]=min(p+dy[ix][0], q*(x/y)+dy[ix+1][0]);
}

int main(){
	int t;
	for(scanf("%d",&t); t--;){
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
		gcd(0,a,b);
		printf("%lld\n", dy[0][a<b]);
	}
	return 0;
}

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