oj.uz

Submission #12315

# Submission time Handle Problem Language Result Execution time Memory
12315 2014-12-26T12:04:26 Z baneling100 Min-cost GCD (GA9_mcg) C++
30 / 100
 160 ms 1100 KB 
#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

int T, Cnt;
long long A, B, P, Q, D[1001][2];

void gcd(long long X, long long Y) {

    if(!Y) {
        printf("%lld\n",min(D[Cnt][0],D[Cnt][1]));
        return;
    }
    Cnt++;
    D[Cnt][0]=min(D[Cnt-1][0]+P,D[Cnt-1][1]+X/Y*Q);
    D[Cnt][1]=D[Cnt-1][0]+X/Y*Q;
    gcd(Y,X%Y);
}

int main(void) {

    int i;

    scanf("%d",&T);
    for(i=1 ; i<=T ; i++) {
        scanf("%lld %lld %lld %lld",&A,&B,&P,&Q);
        Cnt=1;
        if(A>B) {
            D[Cnt][0]=0;
            D[Cnt][1]=INF;
        }
        else if(A<B) {
            D[Cnt][0]=P;
            D[Cnt][1]=0;
        }
        else
            D[Cnt][0]=D[Cnt][1]=0;
        if(A>B)
            gcd(A,B);
        else
            gcd(B,A);
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1100 KB Output is correct
2 Correct 0 ms 1100 KB Output is correct
3 Correct 0 ms 1100 KB Output is correct
4 Correct 0 ms 1100 KB Output is correct
5 Correct 0 ms 1100 KB Output is correct
6 Correct 0 ms 1100 KB Output is correct
7 Correct 0 ms 1100 KB Output is correct
8 Correct 0 ms 1100 KB Output is correct
9 Correct 0 ms 1100 KB Output is correct
10 Correct 0 ms 1100 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1100 KB Output is correct
2 Correct 0 ms 1100 KB Output is correct
3 Correct 0 ms 1100 KB Output is correct
4 Correct 71 ms 1100 KB Output is correct
5 Correct 76 ms 1100 KB Output is correct
6 Correct 60 ms 1100 KB Output is correct
7 Correct 64 ms 1100 KB Output is correct
8 Correct 68 ms 1100 KB Output is correct
9 Correct 66 ms 1100 KB Output is correct
10 Correct 62 ms 1100 KB Output is correct
11 Correct 72 ms 1100 KB Output is correct
12 Correct 0 ms 1100 KB Output is correct
13 Correct 0 ms 1100 KB Output is correct
14 Correct 0 ms 1100 KB Output is correct
15 Correct 0 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 0 ms 1100 KB Output is correct

Subtask #3
0.0 / 27.0

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

Subtask #4
0.0 / 43.0

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