답안 #12321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12321	2014-12-26T12:16:16 Z	baneling100	Min-cost GCD (GA9_mcg)	C++	57 / 100	206 ms	1100 KB

mcg

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

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;
    }
    if(D[Cnt][1]==INF) {
        Cnt++;
        D[Cnt][0]=D[Cnt-1][0]+P;
    }
    else {
        Cnt++;
        if(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);
    }
    D[Cnt][1]=D[Cnt-1][0]+X/Y*Q;
    if(D[Cnt][1]<0)
        D[Cnt][1]=INF;
    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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	1100 KB	Output is correct
2	Correct	77 ms	1100 KB	Output is correct
3	Correct	77 ms	1100 KB	Output is correct
4	Correct	78 ms	1100 KB	Output is correct
5	Correct	67 ms	1100 KB	Output is correct
6	Correct	75 ms	1100 KB	Output is correct
7	Correct	0 ms	1100 KB	Output is correct
8	Correct	72 ms	1100 KB	Output is correct
9	Correct	74 ms	1100 KB	Output is correct
10	Correct	70 ms	1100 KB	Output is correct
11	Correct	90 ms	1100 KB	Output is correct
12	Correct	74 ms	1100 KB	Output is correct
13	Correct	69 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	0 ms	1100 KB	Output is correct
17	Correct	0 ms	1100 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	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	1 ms	1100 KB	Output is correct
9	Correct	0 ms	1100 KB	Output is correct
10	Correct	0 ms	1100 KB	Output is correct
11	Correct	1 ms	1100 KB	Output is correct
12	Correct	0 ms	1100 KB	Output is correct
13	Correct	2 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
18	Correct	0 ms	1100 KB	Output is correct
19	Correct	0 ms	1100 KB	Output is correct
20	Correct	0 ms	1100 KB	Output is correct
21	Correct	0 ms	1100 KB	Output is correct
22	Correct	1 ms	1100 KB	Output is correct
23	Correct	0 ms	1100 KB	Output is correct
24	Correct	2 ms	1100 KB	Output is correct
25	Correct	0 ms	1100 KB	Output is correct
26	Correct	0 ms	1100 KB	Output is correct
27	Correct	0 ms	1100 KB	Output is correct
28	Correct	0 ms	1100 KB	Output is correct
29	Correct	0 ms	1100 KB	Output is correct
30	Correct	1 ms	1100 KB	Output is correct
31	Correct	0 ms	1100 KB	Output is correct

Subtask #4

0.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	187 ms	1100 KB	Output is correct
2	Correct	186 ms	1100 KB	Output is correct
3	Correct	197 ms	1100 KB	Output is correct
4	Correct	163 ms	1100 KB	Output is correct
5	Correct	200 ms	1100 KB	Output is correct
6	Correct	189 ms	1100 KB	Output is correct
7	Correct	175 ms	1100 KB	Output is correct
8	Correct	192 ms	1100 KB	Output is correct
9	Correct	206 ms	1100 KB	Output is correct
10	Correct	185 ms	1100 KB	Output is correct
11	Correct	187 ms	1100 KB	Output is correct
12	Correct	162 ms	1100 KB	Output is correct
13	Correct	0 ms	1100 KB	Output is correct
14	Correct	201 ms	1100 KB	Output is correct
15	Correct	204 ms	1100 KB	Output is correct
16	Correct	199 ms	1100 KB	Output is correct
17	Correct	197 ms	1100 KB	Output is correct
18	Correct	199 ms	1100 KB	Output is correct
19	Incorrect	0 ms	1100 KB	Output isn't correct
20	Halted	0 ms	0 KB	-