oj.uz

Submission #12119

# Submission time Handle Problem Language Result Execution time Memory
12119 2014-12-21T07:24:42 Z tncks0121 Min-cost GCD (GA9_mcg) C++14
41 / 100
 75 ms 32768 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include <map>
using namespace std;
long long a, b, P, Q, C1, C2, TC1, TC2;
typedef long long ll;
const ll INF = (ll)1e18 + 5;
 
typedef pair<ll,ll> pll;
map<pll, ll> tmp[100005];
map<pll, ll> *ans;

ll mul (ll a, ll b) {
    if((double)INF / a < b) return INF;
    return a * b;
}
long long  gcd_cost_quite_fast (long long a, long long  b) {
    if(a == 0 || b == 0)return 0;
    if(ans->count(pll(a,b)) == 1) return (*ans)[pll(a,b)];
     
    long long ret = 0;
     
    if(a >= b) {
        //correct
        ret = gcd_cost_quite_fast(b, a%b) + P;
        ret = min(ret, gcd_cost_quite_fast(a%b, b) + mul(Q, a/b));
    }else {
        ret = gcd_cost_quite_fast(a, b%a) + min(P+P, mul(Q, (b/a)));
    }
     
    return (*ans)[pll(a,b)] = ret;
}
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T--){
        scanf("%lld%lld", &a, &b);
        scanf("%lld%lld", &P, &Q);
        ans = tmp+T;//.clear();
        printf("%lld\n",gcd_cost_quite_fast(a, b));
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5900 KB Output is correct
2 Correct 0 ms 5900 KB Output is correct
3 Correct 0 ms 5900 KB Output is correct
4 Correct 0 ms 5900 KB Output is correct
5 Correct 0 ms 5900 KB Output is correct
6 Correct 0 ms 5900 KB Output is correct
7 Correct 0 ms 5900 KB Output is correct
8 Correct 0 ms 5900 KB Output is correct
9 Correct 0 ms 5900 KB Output is correct
10 Correct 0 ms 5900 KB Output is correct

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 75 ms 32768 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7880 KB Output is correct
2 Correct 10 ms 7880 KB Output is correct
3 Correct 3 ms 7880 KB Output is correct
4 Correct 6 ms 7880 KB Output is correct
5 Correct 5 ms 7880 KB Output is correct
6 Correct 3 ms 7880 KB Output is correct
7 Correct 10 ms 7880 KB Output is correct
8 Correct 10 ms 7880 KB Output is correct
9 Correct 5 ms 7880 KB Output is correct
10 Correct 9 ms 7880 KB Output is correct
11 Correct 0 ms 7880 KB Output is correct
12 Correct 7 ms 7880 KB Output is correct
13 Correct 7 ms 7880 KB Output is correct
14 Correct 0 ms 6428 KB Output is correct
15 Correct 3 ms 6560 KB Output is correct
16 Correct 0 ms 6560 KB Output is correct
17 Correct 6 ms 6428 KB Output is correct
18 Correct 0 ms 6428 KB Output is correct
19 Correct 12 ms 8408 KB Output is correct
20 Correct 12 ms 8408 KB Output is correct
21 Correct 10 ms 8408 KB Output is correct
22 Correct 8 ms 8408 KB Output is correct
23 Correct 6 ms 8408 KB Output is correct
24 Correct 9 ms 8408 KB Output is correct
25 Correct 0 ms 8408 KB Output is correct
26 Correct 4 ms 8408 KB Output is correct
27 Correct 10 ms 8408 KB Output is correct
28 Correct 6 ms 8408 KB Output is correct
29 Correct 4 ms 8408 KB Output is correct
30 Correct 13 ms 8408 KB Output is correct
31 Correct 12 ms 8408 KB Output is correct

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 67 ms 32768 KB Memory limit exceeded
2 Halted 0 ms 0 KB -