| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20135 |
2016-02-27T15:41:34 Z |
hongjun7 |
Min-cost GCD (GA9_mcg) |
C++14 |
|
847 ms |
1212 KB |
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
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;
if (x >= y) {
if ((x / y)*q < d1) d2 = f(x % y, y) + (x / y)*q;
}
else {
if ((y / x)*q < d1) d2 = f(x, y % x) + (y / x)*q;
}
if (d1 > d2) d1 = d2;
d[{x, y}] = d1;
return d1;
}
int main() {
int T;
for (scanf("%d", &T); T--; ) {
scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
d.clear();
printf("%lld\n", f(a, b));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
191 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
178 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
205 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
127 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
198 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
192 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
144 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
180 ms |
1212 KB |
Output is correct |
| 10 |
Correct |
145 ms |
1212 KB |
Output is correct |
| 11 |
Correct |
174 ms |
1212 KB |
Output is correct |
| 12 |
Correct |
118 ms |
1212 KB |
Output is correct |
| 13 |
Correct |
167 ms |
1212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1212 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1212 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
847 ms |
1212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
