Submission #20139

#	Time	Username	Problem	Language	Result	Execution time	Memory
20139		hongjun7	Min-cost GCD (GA9_mcg)	C++14	57 / 100	1000 ms	1220 KiB

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;
map <pair<int, int>, ll> h;
int lim = 2e9;
ll g(int x, int y) {
	if (x == 0 || y == 0) return 0;
	if (h.count({ x, y })) return h[{x, y}];
	ll d1 = g(y, x%y) + p, d2 = 1e18; int m;
	if (x >= y) {
		m = x / y;
		if (m <= d1 / q) d2 = g(x - m*y, y) + m*q;
	}
	else {
		m = y / x;
		if (m <= d1 / q) d2 = g(x, y - m*x) + m*q;
	}
	if (d1 > d2) d1 = d2;
	h[{x, y}] = d1;
	return d1;
}
ll f(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
	if (x > lim || y > lim) {
		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;
	}
	return g((int)(x), (int)(y));
}
int main() {
	int T;
	for (scanf("%d", &T); T--; ) {
		a = _readll(); b = _readll(); p = _readll(); q = _readll();
		d.clear(); h.clear();
		printf("%lld\n", f(a, b));
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 0 / 43