답안 #20138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20138	2016-02-27T15:57:22 Z	hongjun7	Min-cost GCD (GA9_mcg)	C++14	57 / 100	1000 ms	1220 KB

mcg

#include <cstdio>
#include <vector>
#include <map>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static inline int _read() {
	if (_charsNumber < 0) {
		exit(1);
	}
	if (!_charsNumber || _currentChar == _charsNumber) {
		_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
		_currentChar = 0;
	}
	if (_charsNumber <= 0) {
		return -1;
	}
	return _buffer[_currentChar++];
}
static inline ll _readll() {
	int c, s; ll x;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
ll a, b, p, q;
map <pair<ll, ll>, ll> d;
ll f(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
	if (d.count({ x, y })) return d[{x, y}];
	ll d1 = f(y, x%y) + p, d2 = 1e18, m;
	if (x >= y) {
		m = x / y;
		if (m <= d1 / q) d2 = f(x - m*y, y) + m*q;
	}
	else {
		m = y / x;
		if (m <= d1 / q) d2 = f(x, y - m*x) + m*q;
	}
	if (d1 > d2) d1 = d2;
	d[{x, y}] = d1;
	return d1;
}
int main() {
	int T;
	for (scanf("%d", &T); T--; ) {
		a = _readll(); b = _readll(); p = _readll(); q = _readll();
		d.clear();
		printf("%lld\n", f(a, b));
	}
}

Subtask #1

14.0 / 14.0

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

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	1220 KB	Output is correct
2	Correct	160 ms	1220 KB	Output is correct
3	Correct	165 ms	1220 KB	Output is correct
4	Correct	174 ms	1220 KB	Output is correct
5	Correct	84 ms	1220 KB	Output is correct
6	Correct	179 ms	1220 KB	Output is correct
7	Correct	180 ms	1220 KB	Output is correct
8	Correct	109 ms	1220 KB	Output is correct
9	Correct	163 ms	1220 KB	Output is correct
10	Correct	110 ms	1220 KB	Output is correct
11	Correct	153 ms	1220 KB	Output is correct
12	Correct	57 ms	1220 KB	Output is correct
13	Correct	152 ms	1220 KB	Output is correct
14	Correct	0 ms	1220 KB	Output is correct
15	Correct	0 ms	1220 KB	Output is correct
16	Correct	1 ms	1220 KB	Output is correct
17	Correct	2 ms	1220 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	1220 KB	Output is correct
2	Correct	5 ms	1220 KB	Output is correct
3	Correct	5 ms	1220 KB	Output is correct
4	Correct	5 ms	1220 KB	Output is correct
5	Correct	5 ms	1220 KB	Output is correct
6	Correct	0 ms	1220 KB	Output is correct
7	Correct	2 ms	1220 KB	Output is correct
8	Correct	4 ms	1220 KB	Output is correct
9	Correct	5 ms	1220 KB	Output is correct
10	Correct	4 ms	1220 KB	Output is correct
11	Correct	3 ms	1220 KB	Output is correct
12	Correct	5 ms	1220 KB	Output is correct
13	Correct	6 ms	1220 KB	Output is correct
14	Correct	2 ms	1220 KB	Output is correct
15	Correct	0 ms	1220 KB	Output is correct
16	Correct	0 ms	1220 KB	Output is correct
17	Correct	0 ms	1220 KB	Output is correct
18	Correct	0 ms	1220 KB	Output is correct
19	Correct	7 ms	1220 KB	Output is correct
20	Correct	7 ms	1220 KB	Output is correct
21	Correct	7 ms	1220 KB	Output is correct
22	Correct	7 ms	1220 KB	Output is correct
23	Correct	7 ms	1220 KB	Output is correct
24	Correct	6 ms	1220 KB	Output is correct
25	Correct	7 ms	1220 KB	Output is correct
26	Correct	5 ms	1220 KB	Output is correct
27	Correct	6 ms	1220 KB	Output is correct
28	Correct	4 ms	1220 KB	Output is correct
29	Correct	7 ms	1220 KB	Output is correct
30	Correct	7 ms	1220 KB	Output is correct
31	Correct	5 ms	1220 KB	Output is correct

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	844 ms	1220 KB	Output is correct
2	Correct	851 ms	1220 KB	Output is correct
3	Correct	838 ms	1220 KB	Output is correct
4	Correct	845 ms	1220 KB	Output is correct
5	Correct	853 ms	1220 KB	Output is correct
6	Correct	836 ms	1220 KB	Output is correct
7	Correct	851 ms	1220 KB	Output is correct
8	Correct	849 ms	1220 KB	Output is correct
9	Correct	860 ms	1220 KB	Output is correct
10	Correct	863 ms	1220 KB	Output is correct
11	Correct	840 ms	1220 KB	Output is correct
12	Correct	844 ms	1220 KB	Output is correct
13	Correct	860 ms	1220 KB	Output is correct
14	Execution timed out	1000 ms	1220 KB	Program timed out
15	Halted	0 ms	0 KB	-