oj.uz

Submission #12085

# Submission time Handle Problem Language Result Execution time Memory
12085 2014-12-21T00:24:40 Z tncks0121 Min-cost GCD (GA9_mcg) C++14
16 / 100
 88 ms 16784 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 16784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16784 KB Output is correct
2 Correct 87 ms 16784 KB Output is correct
3 Correct 76 ms 16784 KB Output is correct
4 Correct 81 ms 16784 KB Output is correct
5 Correct 72 ms 16784 KB Output is correct
6 Correct 74 ms 16784 KB Output is correct
7 Correct 81 ms 16784 KB Output is correct
8 Correct 85 ms 16784 KB Output is correct
9 Correct 82 ms 16784 KB Output is correct
10 Correct 50 ms 16784 KB Output is correct
11 Correct 50 ms 16784 KB Output is correct
12 Correct 80 ms 16784 KB Output is correct
13 Correct 88 ms 16784 KB Output is correct
14 Correct 0 ms 16784 KB Output is correct
15 Correct 2 ms 16784 KB Output is correct
16 Correct 0 ms 16784 KB Output is correct
17 Correct 2 ms 16784 KB Output is correct

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 16780 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 16780 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -