oj.uz

Submission #12656

# Submission time Handle Problem Language Result Execution time Memory
12656 2014-12-27T13:45:56 Z dohyun0324 Min-cost GCD (GA9_mcg) C++
30 / 100
 279 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(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 93 ms 1084 KB Output is correct
2 Correct 88 ms 1084 KB Output is correct
3 Correct 93 ms 1084 KB Output is correct
4 Correct 93 ms 1084 KB Output is correct
5 Correct 89 ms 1084 KB Output is correct
6 Correct 97 ms 1084 KB Output is correct
7 Correct 71 ms 1084 KB Output is correct
8 Correct 85 ms 1084 KB Output is correct
9 Correct 93 ms 1084 KB Output is correct
10 Correct 89 ms 1084 KB Output is correct
11 Correct 95 ms 1084 KB Output is correct
12 Correct 92 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 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 Incorrect 0 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 279 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -