oj.uz

Submission #12123

# Submission time Handle Problem Language Result Execution time Memory
12123 2014-12-21T07:32:03 Z gs14004 Min-cost GCD (GA9_mcg) C++
30 / 100
 1000 ms 1324 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;

typedef long long lint;
typedef pair<lint,lint> pi;
map<pi,lint> mp;

lint a,b,p,q;

bool calc_valid(lint x, lint y){
    double t = log10(x)+log10(y);
    return t < 17;
}

lint f(lint x, lint y){
    if(x == 0 || y == 0) return 0;
    if(mp.find(pi(x,y)) != mp.end()) return mp[pi(x,y)];
    if(x >= y){
        if(!calc_valid(q,x/y)) return  mp[pi(x,y)] = f(y,x%y) + p;
        else return mp[pi(x,y)] = min(f(y,x%y) + p,f(x%y,y) + q*(x/y));
    }
    else return f(x,y%x) + q*(y/x);
}

void solve(){
    mp.clear();
    scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
    if(a < b){
        lint cand1 = p + f(b,a);
        if(!calc_valid(q,b/a)) printf("%lld\n",cand1);
        else cand1 = min(cand1,f(a,b));
        printf("%lld\n",cand1);
    }
    else printf("%lld\n",f(a,b));
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1324 KB Output is correct
2 Correct 224 ms 1324 KB Output is correct
3 Correct 212 ms 1324 KB Output is correct
4 Correct 229 ms 1324 KB Output is correct
5 Correct 226 ms 1324 KB Output is correct
6 Correct 224 ms 1324 KB Output is correct
7 Correct 224 ms 1324 KB Output is correct
8 Correct 234 ms 1324 KB Output is correct
9 Correct 241 ms 1324 KB Output is correct
10 Correct 231 ms 1324 KB Output is correct
11 Correct 223 ms 1324 KB Output is correct
12 Correct 223 ms 1324 KB Output is correct
13 Correct 220 ms 1324 KB Output is correct
14 Correct 2 ms 1324 KB Output is correct
15 Correct 1 ms 1324 KB Output is correct
16 Correct 2 ms 1324 KB Output is correct
17 Correct 3 ms 1324 KB Output is correct

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1324 KB Program timed out
2 Halted 0 ms 0 KB -