oj.uz

답안 #12124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12124 2014-12-21T07:33:55 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 < 18;
}

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 1324 KB Output is correct
2 Correct 226 ms 1324 KB Output is correct
3 Correct 218 ms 1324 KB Output is correct
4 Correct 224 ms 1324 KB Output is correct
5 Correct 219 ms 1324 KB Output is correct
6 Correct 217 ms 1324 KB Output is correct
7 Correct 226 ms 1324 KB Output is correct
8 Correct 223 ms 1324 KB Output is correct
9 Correct 235 ms 1324 KB Output is correct
10 Correct 216 ms 1324 KB Output is correct
11 Correct 228 ms 1324 KB Output is correct
12 Correct 210 ms 1324 KB Output is correct
13 Correct 224 ms 1324 KB Output is correct
14 Correct 2 ms 1324 KB Output is correct
15 Correct 0 ms 1324 KB Output is correct
16 Correct 0 ms 1324 KB Output is correct
17 Correct 0 ms 1324 KB Output is correct

Subtask #3
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1324 KB Output is correct
2 Incorrect 7 ms 1324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1324 KB Program timed out
2 Halted 0 ms 0 KB -