Submission #12085

#	Time	Username	Problem	Language	Result	Execution time	Memory
12085		tncks0121	Min-cost GCD (GA9_mcg)	C++14	16 / 100	88 ms	16784 KiB

mcg

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stack>
#include <memory.h>
#include <assert.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>

using namespace std;

// for subtask3

int p,q;

int Table[2005][2005];

int solve (int a, int b) {
    if(a * b == 0) return 0;
    if(Table[a][b] >= 0) return Table[a][b];
    return Table[a][b] = min (
        solve(b, a%b) + p,
        (a > b ? solve(a-b, b) : solve(a, b-a)) + q
    );
}

int main() {
    int t; scanf("%d", &t);
    memset(Table, -1, sizeof Table);
    while(t--) {
        int a,b;
        scanf("%d%d%d%d", &a, &b, &p, &q);
        printf("%d\n", solve(a,b));
    }
    return 0;
}

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