제출 #12086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12086		tncks0121	Min-cost GCD (GA9_mcg)	C++14	16 / 100	96 ms	32488 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

long long  p,q;

long long 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%lld%lld", &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