oj.uz

Submission #12659

# Submission time Handle Problem Language Result Execution time Memory
12659 2014-12-27T13:53:46 Z dohyun0324 Min-cost GCD (GA9_mcg) C++
30 / 100
 226 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(q*(a[j-1].x/a[j-1].y)>0 && 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 86 ms 1084 KB Output is correct
2 Correct 95 ms 1084 KB Output is correct
3 Correct 96 ms 1084 KB Output is correct
4 Correct 90 ms 1084 KB Output is correct
5 Correct 92 ms 1084 KB Output is correct
6 Correct 92 ms 1084 KB Output is correct
7 Correct 100 ms 1084 KB Output is correct
8 Correct 82 ms 1084 KB Output is correct
9 Correct 92 ms 1084 KB Output is correct
10 Correct 88 ms 1084 KB Output is correct
11 Correct 97 ms 1084 KB Output is correct
12 Correct 93 ms 1084 KB Output is correct
13 Correct 91 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 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 2 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 1 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct
11 Correct 0 ms 1084 KB Output is correct
12 Incorrect 0 ms 1084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

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