oj.uz

Submission #12111

# Submission time Handle Problem Language Result Execution time Memory
12111 2014-12-21T07:19:17 Z kriii Min-cost GCD (GA9_mcg) C++14
0 / 100
 664 ms 1212 KB 
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;

long long a,b,p,q;

std::map<long long, long long> chk;

long long go(long long a, long long b)
{
	if (a == 0 || b == 0) return 0;
	if (a == b) return p < q ? p : q;
	if (chk.count(a*b+a+b)) return chk[a*b+a+b];
	long long &r = chk[a*b+a+b];
	r = p + go(b,a%b);
	if (a > b){
		long long d = a / b, e = q * d;
		if (q * d / d == q) r = min(r, e + go(a-b*d,b));
	}
	else{
		long long d = b / a, e = q * d;
		if (q * d / d == q) r = min(r, e + go(a,b-a*d));
	}
	return r;
}

int main()
{
	int T; scanf ("%d",&T); while (T--){
		scanf ("%lld %lld %lld %lld",&a,&b,&p,&q);
		chk.clear();
		printf ("%lld\n",go(a,b));
	}

	return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 1212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 1212 KB Output isn't correct
2 Halted 0 ms 0 KB -