oj.uz

Submission #12655

# Submission time Handle Problem Language Result Execution time Memory
12655 2014-12-27T13:44:31 Z dohyun0324 Min-cost GCD (GA9_mcg) C++
30 / 100
 88 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[31];
struct data2
{
    long long mi,ma;
}d[31];
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<=30;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(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(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(dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y);
        if(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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 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 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1084 KB Output is correct
2 Correct 85 ms 1084 KB Output is correct
3 Correct 56 ms 1084 KB Output is correct
4 Correct 88 ms 1084 KB Output is correct
5 Correct 75 ms 1084 KB Output is correct
6 Correct 87 ms 1084 KB Output is correct
7 Correct 84 ms 1084 KB Output is correct
8 Correct 75 ms 1084 KB Output is correct
9 Correct 79 ms 1084 KB Output is correct
10 Correct 84 ms 1084 KB Output is correct
11 Correct 87 ms 1084 KB Output is correct
12 Correct 72 ms 1084 KB Output is correct
13 Correct 84 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
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1084 KB Output is correct
2 Incorrect 1 ms 1084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

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