Submission #12340

#	Time	Username	Problem	Language	Result	Execution time	Memory
12340		baneling100	Min-cost GCD (GA9_mcg)	C++98	100 / 100	625 ms	1208 KiB

mcg

#include <stdio.h>
#include <algorithm>
#include <math.h>
#define INF 0x7fffffffffffffff

using namespace std;

int T, Cnt;
long long A, B, P, Q, D[1001][2];
double LX, LY, LQ, LI=log(INF);

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

    if(!Y) {
        printf("%lld\n",min(D[Cnt][0],D[Cnt][1]));
        return;
    }
    LX=log(X);
    LY=log(Y);
    Cnt++;
    if(LX-LY+LQ>LI || D[Cnt-1][1]+X/Y*Q<0)
        D[Cnt][0]=D[Cnt-1][0]+P;
    else
        D[Cnt][0]=min(D[Cnt-1][0]+P,D[Cnt-1][1]+X/Y*Q);
    if(LX-LY+LQ>LI || D[Cnt-1][0]+X/Y*Q<0)
        D[Cnt][1]=INF;
    else
        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);
        LQ=log(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 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 43 / 43