답안 #12687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12687 2014-12-30T07:30:10 Z gs14004 Min-cost GCD (GA9_mcg) C++
100 / 100
965 ms 1196 KB
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
 
typedef long long lint;
lint dp[100], dp2[100];
 
lint a,b,p,q;
 
inline bool calc_valid(lint x, lint y){
    double t = log10(x)+log10(y);
    return t < 18;
}
 
lint f(lint x, lint y, int step){
    if(x == 0 || y == 0) return 0;
    if(x >= y){
        if(dp[step]) return dp[step];
        if(!calc_valid(q,x/y)) return dp[step] = f(y,x%y,step+1) + p;
        else return dp[step] = min(f(y,x%y,step+1) + p,f(x%y,y,step+1) + q*(x/y));
    }
    else{
      	if(dp2[step]) return dp2[step];
        if(!calc_valid(q,y/x)) return 5e18;
        else return dp2[step] = f(x,y%x,step+1) + q * (y/x);
    }
}
 
void solve(){
    memset(dp,0,sizeof(dp));
    memset(dp2,0,sizeof(dp2));
    scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
    if(a < b) printf("%lld\n",min(p + f(b,a,0),f(a,b,0)));
    else printf("%lld\n",f(a,b,0));
}
 
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Correct 0 ms 1196 KB Output is correct
3 Correct 0 ms 1196 KB Output is correct
4 Correct 0 ms 1196 KB Output is correct
5 Correct 0 ms 1196 KB Output is correct
6 Correct 0 ms 1196 KB Output is correct
7 Correct 0 ms 1196 KB Output is correct
8 Correct 0 ms 1196 KB Output is correct
9 Correct 0 ms 1196 KB Output is correct
10 Correct 0 ms 1196 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 1196 KB Output is correct
2 Correct 197 ms 1196 KB Output is correct
3 Correct 210 ms 1196 KB Output is correct
4 Correct 202 ms 1196 KB Output is correct
5 Correct 204 ms 1196 KB Output is correct
6 Correct 208 ms 1196 KB Output is correct
7 Correct 217 ms 1196 KB Output is correct
8 Correct 210 ms 1196 KB Output is correct
9 Correct 202 ms 1196 KB Output is correct
10 Correct 218 ms 1196 KB Output is correct
11 Correct 211 ms 1196 KB Output is correct
12 Correct 204 ms 1196 KB Output is correct
13 Correct 210 ms 1196 KB Output is correct
14 Correct 2 ms 1196 KB Output is correct
15 Correct 0 ms 1196 KB Output is correct
16 Correct 0 ms 1196 KB Output is correct
17 Correct 0 ms 1196 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1196 KB Output is correct
2 Correct 3 ms 1196 KB Output is correct
3 Correct 5 ms 1196 KB Output is correct
4 Correct 3 ms 1196 KB Output is correct
5 Correct 5 ms 1196 KB Output is correct
6 Correct 3 ms 1196 KB Output is correct
7 Correct 5 ms 1196 KB Output is correct
8 Correct 5 ms 1196 KB Output is correct
9 Correct 5 ms 1196 KB Output is correct
10 Correct 6 ms 1196 KB Output is correct
11 Correct 5 ms 1196 KB Output is correct
12 Correct 5 ms 1196 KB Output is correct
13 Correct 4 ms 1196 KB Output is correct
14 Correct 0 ms 1196 KB Output is correct
15 Correct 1 ms 1196 KB Output is correct
16 Correct 2 ms 1196 KB Output is correct
17 Correct 0 ms 1196 KB Output is correct
18 Correct 1 ms 1196 KB Output is correct
19 Correct 6 ms 1196 KB Output is correct
20 Correct 5 ms 1196 KB Output is correct
21 Correct 3 ms 1196 KB Output is correct
22 Correct 6 ms 1196 KB Output is correct
23 Correct 6 ms 1196 KB Output is correct
24 Correct 5 ms 1196 KB Output is correct
25 Correct 5 ms 1196 KB Output is correct
26 Correct 6 ms 1196 KB Output is correct
27 Correct 3 ms 1196 KB Output is correct
28 Correct 5 ms 1196 KB Output is correct
29 Correct 3 ms 1196 KB Output is correct
30 Correct 2 ms 1196 KB Output is correct
31 Correct 3 ms 1196 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 841 ms 1196 KB Output is correct
2 Correct 837 ms 1196 KB Output is correct
3 Correct 856 ms 1196 KB Output is correct
4 Correct 845 ms 1196 KB Output is correct
5 Correct 837 ms 1196 KB Output is correct
6 Correct 837 ms 1196 KB Output is correct
7 Correct 849 ms 1196 KB Output is correct
8 Correct 821 ms 1196 KB Output is correct
9 Correct 857 ms 1196 KB Output is correct
10 Correct 825 ms 1196 KB Output is correct
11 Correct 811 ms 1196 KB Output is correct
12 Correct 828 ms 1196 KB Output is correct
13 Correct 829 ms 1196 KB Output is correct
14 Correct 936 ms 1196 KB Output is correct
15 Correct 911 ms 1196 KB Output is correct
16 Correct 935 ms 1196 KB Output is correct
17 Correct 937 ms 1196 KB Output is correct
18 Correct 936 ms 1196 KB Output is correct
19 Correct 270 ms 1196 KB Output is correct
20 Correct 281 ms 1196 KB Output is correct
21 Correct 273 ms 1196 KB Output is correct
22 Correct 269 ms 1196 KB Output is correct
23 Correct 354 ms 1196 KB Output is correct
24 Correct 371 ms 1196 KB Output is correct
25 Correct 350 ms 1196 KB Output is correct
26 Correct 349 ms 1196 KB Output is correct
27 Correct 370 ms 1196 KB Output is correct
28 Correct 962 ms 1196 KB Output is correct
29 Correct 907 ms 1196 KB Output is correct
30 Correct 952 ms 1196 KB Output is correct
31 Correct 868 ms 1196 KB Output is correct
32 Correct 905 ms 1196 KB Output is correct
33 Correct 936 ms 1196 KB Output is correct
34 Correct 918 ms 1196 KB Output is correct
35 Correct 965 ms 1196 KB Output is correct