Submission #12149

#	Time	Username	Problem	Language	Result	Execution time	Memory
12149		gs13105	Min-cost GCD (GA9_mcg)	C++98	14 / 100	69 ms	16724 KiB

mcg

#include <stdio.h>

int mem[2001][2001];

inline int mn(int a,int b)
{
	return a<b?a:b;
}

int main()
{
	int a,b,p,q,m,t,i,j,k;
	scanf("%d",&t);
	for(k=0;k<t;k++)
	{
		scanf("%d%d%d%d",&a,&b,&p,&q);
		if(t>100&&k)
		{
			printf("%d\n",mem[a][b]);
			continue;
		}
		m=a>b?a:b;
		for(j=1;j<=m;j++)
			for(i=1;i<=m;i++)
				mem[i][j]=mn(p+mem[j][i%j],q+(i>=j?mem[i-j][j]:mem[i][j-i]));
		printf("%d\n",mem[a][b]);
	}
	return 0;
}

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