oj.uz

Submission #12087

# Submission time Handle Problem Language Result Execution time Memory
12087 2014-12-21T00:33:19 Z tncks0121 Min-cost GCD (GA9_mcg) C++14
57 / 100
 1000 ms 1212 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> 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.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 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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 1212 KB Output is correct
2 Correct 165 ms 1212 KB Output is correct
3 Correct 167 ms 1212 KB Output is correct
4 Correct 164 ms 1212 KB Output is correct
5 Correct 177 ms 1212 KB Output is correct
6 Correct 162 ms 1212 KB Output is correct
7 Correct 176 ms 1212 KB Output is correct
8 Correct 177 ms 1212 KB Output is correct
9 Correct 174 ms 1212 KB Output is correct
10 Correct 168 ms 1212 KB Output is correct
11 Correct 166 ms 1212 KB Output is correct
12 Correct 166 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 2 ms 1212 KB Output is correct
16 Correct 2 ms 1212 KB Output is correct
17 Correct 2 ms 1212 KB Output is correct

Subtask #3
27.0 / 27.0

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

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 1212 KB Output is correct
2 Correct 785 ms 1212 KB Output is correct
3 Correct 799 ms 1212 KB Output is correct
4 Correct 812 ms 1212 KB Output is correct
5 Correct 807 ms 1212 KB Output is correct
6 Correct 800 ms 1212 KB Output is correct
7 Correct 780 ms 1212 KB Output is correct
8 Correct 798 ms 1212 KB Output is correct
9 Correct 808 ms 1212 KB Output is correct
10 Correct 799 ms 1212 KB Output is correct
11 Correct 784 ms 1212 KB Output is correct
12 Correct 792 ms 1212 KB Output is correct
13 Correct 796 ms 1212 KB Output is correct
14 Execution timed out 1000 ms 1212 KB Program timed out
15 Halted 0 ms 0 KB -