Submission #18557

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

mcg

#include<stdio.h>
#include<memory.h>

typedef long long lld;

lld a, b, p, q, dy[70][2], chk[70][2];

lld gcd(int ix, lld a, lld b){
	if(!a || !b)return 0;
	if(a<b){
		if(chk[ix][0])return dy[ix][0];
		chk[ix][0]=1, dy[ix][0]=gcd(ix+1,a,b%a)+2*p;
		if(b/a <= (2*p)/q)dy[ix][0]=gcd(ix+1,a,b%a)+(b/a)*q;
		return dy[ix][0];
	}
	else{
		if(chk[ix][1])return dy[ix][1];
		chk[ix][1]=1, dy[ix][1]=gcd(ix+1,b,a%b)+p;
		lld tmp=dy[ix][1]-gcd(ix+1,a%b,b);
		if(a/b <= tmp/q)dy[ix][1]-=tmp-(a/b)*q;
		return dy[ix][1];
	}
	return 0;
}

int main(){
	int t;
	for(scanf("%d",&t);t--;){
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
		memset(chk,0,sizeof(chk));
		printf("%lld\n", gcd(0,a,b));
	}
	return 0;
}

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