oj.uz

답안 #20143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20143 2016-02-28T00:18:20 Z hongjun7 Min-cost GCD (GA9_mcg) C++14
30 / 100
 117 ms 1088 KB 
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#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, d[222][2];
void f(ll x, ll y, int z) {
	if (x < y) swap(x, y);
	if (x == 0 || y == 0) {
		d[z][0] = d[z][1] = 0;
		return;
	}
	f(y, x%y, z + 1);
	d[z][0] = min(p + d[z + 1][0], q*(x / y) + d[z + 1][1]);
	d[z][1] = min(p + d[z][0], q*(x / y) + d[z + 1][0]);
}
int main() {
	int T;
	for (scanf("%d", &T); T--; ) {
		a = _readll(); b = _readll(); p = _readll(); q = _readll();
		f(a, b, 0);
		printf("%lld\n", d[0][a < b]);
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 31 ms 1088 KB Output is correct
3 Correct 30 ms 1088 KB Output is correct
4 Correct 0 ms 1088 KB Output is correct
5 Correct 44 ms 1088 KB Output is correct
6 Correct 0 ms 1088 KB Output is correct
7 Correct 0 ms 1088 KB Output is correct
8 Correct 29 ms 1088 KB Output is correct
9 Correct 0 ms 1088 KB Output is correct
10 Correct 36 ms 1088 KB Output is correct
11 Correct 42 ms 1088 KB Output is correct
12 Correct 35 ms 1088 KB Output is correct
13 Correct 44 ms 1088 KB Output is correct
14 Correct 0 ms 1088 KB Output is correct
15 Correct 0 ms 1088 KB Output is correct
16 Correct 0 ms 1088 KB Output is correct
17 Correct 0 ms 1088 KB Output is correct

Subtask #3
0.0 / 27.0

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

Subtask #4
0.0 / 43.0

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