답안 #12661 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12661	2014-12-27T14:03:57 Z	dohyun0324	Min-cost GCD (GA9_mcg)	C++	100 / 100	306 ms	1084 KB

#include<stdio.h>
#define M 922337203685477580LL
int t,w;
long long x,y,p,q,dap;
struct data
{
    long long x,y;
}a[101];
struct data2
{
    long long mi,ma;
}d[101];
void gcd(long long x,long long y)
{
    w++; a[w].x=x; a[w].y=y;
    if(x%y==0) return;
    gcd(y,x%y);
}
int main()
{
    int i,j;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        dap=M; w=0;
        for(j=1;j<=100;j++) d[j].ma=M, d[j].mi=M;
        scanf("%lld %lld %lld %lld",&x,&y,&p,&q);
        if(x==y){
            if(p>q) printf("%lld\n",q);
            else printf("%lld\n",p);
            continue;
        }
        if(x>y) gcd(x,y);
        else gcd(y,x);
        if(x>y) d[1].ma=0;
        else d[1].mi=0, d[1].ma=p;
        for(j=2;j<=w;j++)
        {
            if(q<=p*100/(a[j-1].x/a[j-1].y+1)+1 && d[j].mi>d[j-1].ma+q*(a[j-1].x/a[j-1].y)) d[j].mi=d[j-1].ma+q*(a[j-1].x/a[j-1].y);
            if(d[j].ma>d[j-1].ma+p) d[j].ma=d[j-1].ma+p;
            if(q<=p*100/(a[j-1].x/a[j-1].y+1)+1 &&  d[j].ma>d[j-1].mi+q*(a[j-1].x/a[j-1].y)) d[j].ma=d[j-1].mi+q*(a[j-1].x/a[j-1].y);
            if(d[j].ma>d[j].mi+p) d[j].ma=d[j].mi+p;
        }
        if(q<=p*100/(a[w].x/a[w].y+1)+1 && dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y);
        if(q<=p*100/(a[w].x/a[w].y+1)+1 &&  dap>d[w].ma+q*(a[w].x/a[w].y)) dap=d[w].ma+q*(a[w].x/a[w].y);
        if(dap>d[w].ma+p) dap=d[w].ma+p;
        if(dap>d[w].mi+p+p) dap=d[w].mi+p+p;
        printf("%lld\n",dap);
    }
    return 0;
}

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	98 ms	1084 KB	Output is correct
2	Correct	102 ms	1084 KB	Output is correct
3	Correct	101 ms	1084 KB	Output is correct
4	Correct	100 ms	1084 KB	Output is correct
5	Correct	93 ms	1084 KB	Output is correct
6	Correct	102 ms	1084 KB	Output is correct
7	Correct	99 ms	1084 KB	Output is correct
8	Correct	95 ms	1084 KB	Output is correct
9	Correct	87 ms	1084 KB	Output is correct
10	Correct	91 ms	1084 KB	Output is correct
11	Correct	107 ms	1084 KB	Output is correct
12	Correct	98 ms	1084 KB	Output is correct
13	Correct	106 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	0 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	2 ms	1084 KB	Output is correct
3	Correct	1 ms	1084 KB	Output is correct
4	Correct	0 ms	1084 KB	Output is correct
5	Correct	0 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	0 ms	1084 KB	Output is correct
10	Correct	1 ms	1084 KB	Output is correct
11	Correct	0 ms	1084 KB	Output is correct
12	Correct	0 ms	1084 KB	Output is correct
13	Correct	1 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
18	Correct	0 ms	1084 KB	Output is correct
19	Correct	0 ms	1084 KB	Output is correct
20	Correct	2 ms	1084 KB	Output is correct
21	Correct	1 ms	1084 KB	Output is correct
22	Correct	0 ms	1084 KB	Output is correct
23	Correct	0 ms	1084 KB	Output is correct
24	Correct	2 ms	1084 KB	Output is correct
25	Correct	1 ms	1084 KB	Output is correct
26	Correct	2 ms	1084 KB	Output is correct
27	Correct	1 ms	1084 KB	Output is correct
28	Correct	0 ms	1084 KB	Output is correct
29	Correct	1 ms	1084 KB	Output is correct
30	Correct	0 ms	1084 KB	Output is correct
31	Correct	0 ms	1084 KB	Output is correct

Subtask #4
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	280 ms	1084 KB	Output is correct
2	Correct	264 ms	1084 KB	Output is correct
3	Correct	244 ms	1084 KB	Output is correct
4	Correct	266 ms	1084 KB	Output is correct
5	Correct	285 ms	1084 KB	Output is correct
6	Correct	263 ms	1084 KB	Output is correct
7	Correct	276 ms	1084 KB	Output is correct
8	Correct	266 ms	1084 KB	Output is correct
9	Correct	274 ms	1084 KB	Output is correct
10	Correct	280 ms	1084 KB	Output is correct
11	Correct	264 ms	1084 KB	Output is correct
12	Correct	265 ms	1084 KB	Output is correct
13	Correct	237 ms	1084 KB	Output is correct
14	Correct	300 ms	1084 KB	Output is correct
15	Correct	286 ms	1084 KB	Output is correct
16	Correct	287 ms	1084 KB	Output is correct
17	Correct	271 ms	1084 KB	Output is correct
18	Correct	279 ms	1084 KB	Output is correct
19	Correct	149 ms	1084 KB	Output is correct
20	Correct	141 ms	1084 KB	Output is correct
21	Correct	150 ms	1084 KB	Output is correct
22	Correct	138 ms	1084 KB	Output is correct
23	Correct	159 ms	1084 KB	Output is correct
24	Correct	151 ms	1084 KB	Output is correct
25	Correct	159 ms	1084 KB	Output is correct
26	Correct	164 ms	1084 KB	Output is correct
27	Correct	167 ms	1084 KB	Output is correct
28	Correct	306 ms	1084 KB	Output is correct
29	Correct	283 ms	1084 KB	Output is correct
30	Correct	298 ms	1084 KB	Output is correct
31	Correct	277 ms	1084 KB	Output is correct
32	Correct	280 ms	1084 KB	Output is correct
33	Correct	287 ms	1084 KB	Output is correct
34	Correct	279 ms	1084 KB	Output is correct
35	Correct	304 ms	1084 KB	Output is correct

답안 #12661

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