oj.uz

Submission #12086

# Submission time Handle Problem Language Result Execution time Memory
12086 2014-12-21T00:25:12 Z tncks0121 Min-cost GCD (GA9_mcg) C++14
16 / 100
 96 ms 32488 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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 32488 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 66 ms 32488 KB Output is correct
2 Correct 96 ms 32488 KB Output is correct
3 Correct 86 ms 32488 KB Output is correct
4 Correct 83 ms 32488 KB Output is correct
5 Correct 88 ms 32488 KB Output is correct
6 Correct 96 ms 32488 KB Output is correct
7 Correct 93 ms 32488 KB Output is correct
8 Correct 87 ms 32488 KB Output is correct
9 Correct 78 ms 32488 KB Output is correct
10 Correct 91 ms 32488 KB Output is correct
11 Correct 91 ms 32488 KB Output is correct
12 Correct 88 ms 32488 KB Output is correct
13 Correct 92 ms 32488 KB Output is correct
14 Correct 0 ms 32488 KB Output is correct
15 Correct 9 ms 32488 KB Output is correct
16 Correct 3 ms 32488 KB Output is correct
17 Correct 4 ms 32488 KB Output is correct

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 32484 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 32484 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -