답안 #12689 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12689	2014-12-30T07:33:46 Z	gs14004	Min-cost GCD (GA9_mcg)	C++	100 / 100	528 ms	1084 KB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
typedef long long lint;
lint dp[100], dp2[100];
lint pow[19] = {1,0}; 
lint a,b,p,q;

inline bool calc_valid(lint x, lint y){
  	int t = lower_bound(pow,pow+19,x) - pow + lower_bound(pow,pow+19,y) - pow;
    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,-1,sizeof(dp));
    memset(dp2,-1,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(){
  	for(int i=1; i<=18; i++) pow[i] = pow[i-1] * 10;
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}

Subtask #1
14.0 / 14.0

#	결과	메모리	Grader output
1	Correct	1084 KB	Output is correct
2	Correct	1084 KB	Output is correct
3	Correct	1084 KB	Output is correct
4	Correct	1084 KB	Output is correct
5	Correct	1084 KB	Output is correct
6	Correct	1084 KB	Output is correct
7	Correct	1084 KB	Output is correct
8	Correct	1084 KB	Output is correct
9	Correct	1084 KB	Output is correct
10	Correct	1084 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	1084 KB	Output is correct
2	Correct	139 ms	1084 KB	Output is correct
3	Correct	140 ms	1084 KB	Output is correct
4	Correct	138 ms	1084 KB	Output is correct
5	Correct	132 ms	1084 KB	Output is correct
6	Correct	127 ms	1084 KB	Output is correct
7	Correct	126 ms	1084 KB	Output is correct
8	Correct	129 ms	1084 KB	Output is correct
9	Correct	140 ms	1084 KB	Output is correct
10	Correct	139 ms	1084 KB	Output is correct
11	Correct	136 ms	1084 KB	Output is correct
12	Correct	125 ms	1084 KB	Output is correct
13	Correct	137 ms	1084 KB	Output is correct
14	Correct	0 ms	1084 KB	Output is correct
15	Correct	0 ms	1084 KB	Output is correct
16	Correct	0 ms	1084 KB	Output is correct
17	Correct	1 ms	1084 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1084 KB	Output is correct
2	Correct	0 ms	1084 KB	Output is correct
3	Correct	3 ms	1084 KB	Output is correct
4	Correct	3 ms	1084 KB	Output is correct
5	Correct	2 ms	1084 KB	Output is correct
6	Correct	0 ms	1084 KB	Output is correct
7	Correct	0 ms	1084 KB	Output is correct
8	Correct	2 ms	1084 KB	Output is correct
9	Correct	2 ms	1084 KB	Output is correct
10	Correct	3 ms	1084 KB	Output is correct
11	Correct	3 ms	1084 KB	Output is correct
12	Correct	3 ms	1084 KB	Output is correct
13	Correct	3 ms	1084 KB	Output is correct
14	Correct	2 ms	1084 KB	Output is correct
15	Correct	0 ms	1084 KB	Output is correct
16	Correct	1 ms	1084 KB	Output is correct
17	Correct	0 ms	1084 KB	Output is correct
18	Correct	0 ms	1084 KB	Output is correct
19	Correct	2 ms	1084 KB	Output is correct
20	Correct	0 ms	1084 KB	Output is correct
21	Correct	3 ms	1084 KB	Output is correct
22	Correct	3 ms	1084 KB	Output is correct
23	Correct	2 ms	1084 KB	Output is correct
24	Correct	2 ms	1084 KB	Output is correct
25	Correct	2 ms	1084 KB	Output is correct
26	Correct	3 ms	1084 KB	Output is correct
27	Correct	3 ms	1084 KB	Output is correct
28	Correct	2 ms	1084 KB	Output is correct
29	Correct	3 ms	1084 KB	Output is correct
30	Correct	3 ms	1084 KB	Output is correct
31	Correct	3 ms	1084 KB	Output is correct

Subtask #4
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	483 ms	1084 KB	Output is correct
2	Correct	475 ms	1084 KB	Output is correct
3	Correct	486 ms	1084 KB	Output is correct
4	Correct	485 ms	1084 KB	Output is correct
5	Correct	489 ms	1084 KB	Output is correct
6	Correct	488 ms	1084 KB	Output is correct
7	Correct	506 ms	1084 KB	Output is correct
8	Correct	463 ms	1084 KB	Output is correct
9	Correct	495 ms	1084 KB	Output is correct
10	Correct	466 ms	1084 KB	Output is correct
11	Correct	473 ms	1084 KB	Output is correct
12	Correct	483 ms	1084 KB	Output is correct
13	Correct	479 ms	1084 KB	Output is correct
14	Correct	492 ms	1084 KB	Output is correct
15	Correct	505 ms	1084 KB	Output is correct
16	Correct	505 ms	1084 KB	Output is correct
17	Correct	506 ms	1084 KB	Output is correct
18	Correct	494 ms	1084 KB	Output is correct
19	Correct	186 ms	1084 KB	Output is correct
20	Correct	185 ms	1084 KB	Output is correct
21	Correct	172 ms	1084 KB	Output is correct
22	Correct	174 ms	1084 KB	Output is correct
23	Correct	222 ms	1084 KB	Output is correct
24	Correct	213 ms	1084 KB	Output is correct
25	Correct	219 ms	1084 KB	Output is correct
26	Correct	214 ms	1084 KB	Output is correct
27	Correct	215 ms	1084 KB	Output is correct
28	Correct	502 ms	1084 KB	Output is correct
29	Correct	487 ms	1084 KB	Output is correct
30	Correct	528 ms	1084 KB	Output is correct
31	Correct	487 ms	1084 KB	Output is correct
32	Correct	499 ms	1084 KB	Output is correct
33	Correct	488 ms	1084 KB	Output is correct
34	Correct	506 ms	1084 KB	Output is correct
35	Correct	513 ms	1084 KB	Output is correct

답안 #12689

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 16.0 / 16.0

Subtask #3 27.0 / 27.0

Subtask #4 43.0 / 43.0

Subtask #1
14.0 / 14.0

Subtask #2
16.0 / 16.0

Subtask #3
27.0 / 27.0

Subtask #4
43.0 / 43.0