Submission #12208

#	Time	Username	Problem	Language	Result	Execution time	Memory
12208		qja0950	Min-cost GCD (GA9_mcg)	C++98	100 / 100	301 ms	1084 KiB

mcg

//
//  main.cpp
//  2. Min-cost GCD (mcg)
//
//  Created by KJBS2 on 2014. 12. 24..
//  Copyright (c) 2014년 KJBS2. All rights reserved.
//

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long ll;

#define MAX_LL ((ll)1*0x7fffffff*0x7fffffff)

ll A, B, P, Q;
ll X, Y, Z, W;
void PROCESS() {
    scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
    X = 0; Y = MAX_LL;
    for(; A!=0 && B!=0;) {
        ll C = A % B, D = A / B;
        
        Z = X + P;
        if( (MAX_LL - X) / Q >= D) W = X + D * Q;
        else W = MAX_LL;
        
        if(Y != MAX_LL) {
            ll temp;
            temp = Y + P + P;
            Z = min(Z, temp);
            if( (MAX_LL - Y) / Q >= D) temp = Y + D * Q;
            else temp = MAX_LL;
            Z = min(Z, temp);
            if( (MAX_LL - Y - P) / Q >= D) temp = Y + P + D * Q;
            else temp = MAX_LL;
            W = min(W, temp);
        }
        X = Z;
        Y = W;
        
        A = B; B = C;
    }
    
    printf("%lld\n", min(X, Y) );
}

int main() {
    int T; scanf("%d", &T);
    for(int i=0; i<T; i++)
        PROCESS();
    
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43