Submission #199846

#	Time	Username	Problem	Language	Result	Execution time	Memory
199846		human1234	Min-cost GCD (GA9_mcg)	C++14	0 / 100	340 ms	2144 KiB

mcg

#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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 27
• Subtask 4: 0 / 43