Submission #20144

#	Time	Username	Problem	Language	Result	Execution time	Memory
20144		hongjun7	Min-cost GCD (GA9_mcg)	C++14	100 / 100	265 ms	1088 KiB

mcg

#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);
	if ((p + d[z + 1][0] - d[z + 1][1]) / q >= x / y) d[z][0] = q*(x / y) + d[z + 1][1];
	else d[z][0] = p + d[z + 1][0];
	if ((p + d[z][0] - d[z + 1][0]) / q >= x / y) d[z][1] = q*(x / y) + d[z + 1][0];
	else d[z][1] = p + d[z][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 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43