oj.uz

Submission #199846

# Submission time Handle Problem Language Result Execution time Memory
199846 2020-02-03T16:35:39 Z human1234 Min-cost GCD (GA9_mcg) C++14
0 / 100
 340 ms 2144 KB 
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main() {
    ios::sync_with_stdio(false);
    
    int t;

    cin >> t;
    while (t--) {
        ll a, b, p, q;
        vpll v;

        cin >> a >> b >> p >> q;
        v.resize(100);
        if (a > b) {
            v[0] = {0, -1};
        } else {
            ll t = a;

            a = b;
            b = t;
            v[0] = {p, 0};
        }

        int c = 0;

        while (a && b) {
            ll k = a / b, r = a % b;
            pll past = v[c], next;
            
            if (past.second == -1) {
                next = {p, k * q};
            } else {
                ll f, s;

                f = min(past.first + p, past.second + k * q);
                s = min(past.first + k * q, past.second + p + k * q);
                next = {f, s};
            }

            c++;
            v[c] = next;

            a = b;
            b = r;
        }

        cout << min(v[c].first, v[c].second) << "\n";
    }
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Incorrect 8 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

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