Submission #20138

#TimeUsernameProblemLanguageResultExecution timeMemory
20138hongjun7Min-cost GCD (GA9_mcg)C++14
57 / 100
1000 ms1220 KiB
#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)); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...