Submission #12150

#	Time	Username	Problem	Language	Result	Execution time	Memory
12150		gs13105	Min-cost GCD (GA9_mcg)	C++98	30 / 100	108 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);
	if(t>100)
	{
		scanf("%d%d%d%d",&a,&b,&p,&q);
		for(j=1;j<=2000;j++)
			for(i=1;i<=2000;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]);
		for(i=0;i<t-1;i++)
		{
			scanf("%d%d%*d%*d",&a,&b);
			printf("%d\n",mem[a][b]);
		}
		return 0;
	}
	for(k=0;k<t;k++)
	{
		scanf("%d%d%d%d",&a,&b,&p,&q);
		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: 16 / 16
• Subtask 3: 0 / 27
• Subtask 4: 0 / 43