oj.uz

Submission #12658

# Submission time Handle Problem Language Result Execution time Memory
12658 2014-12-27T13:52:13 Z dohyun0324 Min-cost GCD (GA9_mcg) C++
30 / 100
 214 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*(a[j-1].x/a[j-1].y)>0 && 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(q*(a[j-1].x/a[j-1].y)>0 && dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y);
        if(q*(a[j-1].x/a[j-1].y)>0 && 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 68 ms 1084 KB Output is correct
2 Correct 72 ms 1084 KB Output is correct
3 Correct 96 ms 1084 KB Output is correct
4 Correct 95 ms 1084 KB Output is correct
5 Correct 90 ms 1084 KB Output is correct
6 Correct 95 ms 1084 KB Output is correct
7 Correct 95 ms 1084 KB Output is correct
8 Correct 87 ms 1084 KB Output is correct
9 Correct 102 ms 1084 KB Output is correct
10 Correct 94 ms 1084 KB Output is correct
11 Correct 90 ms 1084 KB Output is correct
12 Correct 85 ms 1084 KB Output is correct
13 Correct 94 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
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Incorrect 2 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 214 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -