| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20139 |
2016-02-27T16:09:32 Z |
hongjun7 |
Min-cost GCD (GA9_mcg) |
C++14 |
|
1000 ms |
1220 KB |
#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));
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
1220 KB |
Output is correct |
| 2 |
Correct |
145 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
150 ms |
1220 KB |
Output is correct |
| 4 |
Correct |
152 ms |
1220 KB |
Output is correct |
| 5 |
Correct |
84 ms |
1220 KB |
Output is correct |
| 6 |
Correct |
162 ms |
1220 KB |
Output is correct |
| 7 |
Correct |
160 ms |
1220 KB |
Output is correct |
| 8 |
Correct |
98 ms |
1220 KB |
Output is correct |
| 9 |
Correct |
154 ms |
1220 KB |
Output is correct |
| 10 |
Correct |
110 ms |
1220 KB |
Output is correct |
| 11 |
Correct |
144 ms |
1220 KB |
Output is correct |
| 12 |
Correct |
87 ms |
1220 KB |
Output is correct |
| 13 |
Correct |
140 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 |
0 ms |
1220 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1220 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1220 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1220 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1220 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1220 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1220 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1220 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1220 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1220 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1220 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1220 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1220 KB |
Output is correct |
| 15 |
Correct |
2 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 |
3 ms |
1220 KB |
Output is correct |
| 20 |
Correct |
7 ms |
1220 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1220 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1220 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1220 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1220 KB |
Output is correct |
| 25 |
Correct |
6 ms |
1220 KB |
Output is correct |
| 26 |
Correct |
5 ms |
1220 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1220 KB |
Output is correct |
| 28 |
Correct |
6 ms |
1220 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1220 KB |
Output is correct |
| 30 |
Correct |
5 ms |
1220 KB |
Output is correct |
| 31 |
Correct |
5 ms |
1220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
789 ms |
1220 KB |
Output is correct |
| 2 |
Correct |
798 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
779 ms |
1220 KB |
Output is correct |
| 4 |
Correct |
802 ms |
1220 KB |
Output is correct |
| 5 |
Correct |
792 ms |
1220 KB |
Output is correct |
| 6 |
Correct |
805 ms |
1220 KB |
Output is correct |
| 7 |
Correct |
773 ms |
1220 KB |
Output is correct |
| 8 |
Correct |
782 ms |
1220 KB |
Output is correct |
| 9 |
Correct |
805 ms |
1220 KB |
Output is correct |
| 10 |
Correct |
807 ms |
1220 KB |
Output is correct |
| 11 |
Correct |
766 ms |
1220 KB |
Output is correct |
| 12 |
Correct |
785 ms |
1220 KB |
Output is correct |
| 13 |
Correct |
787 ms |
1220 KB |
Output is correct |
| 14 |
Execution timed out |
1000 ms |
1220 KB |
Program timed out |
| 15 |
Halted |
0 ms |
0 KB |
- |
