답안 #12172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12172	2014-12-21T14:19:46 Z	imsifile	Min-cost GCD (GA9_mcg)	C++	30 / 100	180 ms	1084 KB

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.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1084 KB	Output is correct
2	Correct	0 ms	1084 KB	Output is correct
3	Correct	0 ms	1084 KB	Output is correct
4	Correct	0 ms	1084 KB	Output is correct
5	Correct	0 ms	1084 KB	Output is correct
6	Correct	0 ms	1084 KB	Output is correct
7	Correct	0 ms	1084 KB	Output is correct
8	Correct	0 ms	1084 KB	Output is correct
9	Correct	0 ms	1084 KB	Output is correct
10	Correct	0 ms	1084 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	1084 KB	Output is correct
2	Correct	58 ms	1084 KB	Output is correct
3	Correct	56 ms	1084 KB	Output is correct
4	Correct	74 ms	1084 KB	Output is correct
5	Correct	67 ms	1084 KB	Output is correct
6	Correct	0 ms	1084 KB	Output is correct
7	Correct	73 ms	1084 KB	Output is correct
8	Correct	66 ms	1084 KB	Output is correct
9	Correct	79 ms	1084 KB	Output is correct
10	Correct	71 ms	1084 KB	Output is correct
11	Correct	71 ms	1084 KB	Output is correct
12	Correct	51 ms	1084 KB	Output is correct
13	Correct	71 ms	1084 KB	Output is correct
14	Correct	0 ms	1084 KB	Output is correct
15	Correct	0 ms	1084 KB	Output is correct
16	Correct	0 ms	1084 KB	Output is correct
17	Correct	1 ms	1084 KB	Output is correct

Subtask #3

0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1084 KB	Output is correct
2	Incorrect	1 ms	1084 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	180 ms	1084 KB	Output isn't correct
2	Halted	0 ms	0 KB	-