Submission #12122

#	Time	Username	Problem	Language	Result	Execution time	Memory
12122		gs14004	Min-cost GCD (GA9_mcg)	C++98	0 / 100	1000 ms	1324 KiB

mcg

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;

typedef long long lint;
typedef pair<lint,lint> pi;
map<pi,lint> mp;

lint a,b,p,q;

bool calc_valid(lint x, lint y){
    double t = log10(x)+log10(y);
    return t < 17;
}

lint f(lint x, lint y){
    if(x == 0 || y == 0) return 0;
    if(mp.find(pi(x,y)) != mp.end()) return mp[pi(x,y)];
    if(x >= y){
        if(!calc_valid(q,x/y)) return  mp[pi(x,y)] = f(y,x%y) + p;
        else return mp[pi(x,y)] = min(f(y,x%y) + p,f(x%y,y) + q*(x/y));
    }
    else return f(x,y%x) + q*(y/x);
}

void solve(){
    mp.clear();
    scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
    if(a < b){
        lint cand1 = p + f(b,a);
        if(!calc_valid(q,b/a)) printf("%lld\n",cand1);
        else cand1 = min(cand1,f(a,b));
        printf("%lld",cand1);
    }
    else printf("%lld\n",f(a,b));
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        solve();
    }
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 16
• Subtask 3: 0 / 27
• Subtask 4: 0 / 43