# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27207 | TAMREF | Min-cost GCD (GA9_mcg) | C++11 | 256 ms | 2024 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=300;
ll x,y,p,q;
ll eu[mx], dp[2*mx];
int E;
void workgcd(ll u, ll v){
eu[E++]=v;
if(!v) return;
workgcd(v,u%v);
}
int main(){
int T;
for(scanf("%d",&T);T--;){
scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
E=0;
fill(dp,dp+2*mx,0);
eu[E++]=max(x,y);
workgcd(max(x,y),min(x,y));
for(int i=E-3;i>=0;i--){
dp[2*i]=min(dp[2*i+2]+p,dp[2*i+3]+q*(eu[i]/eu[i+1]));
dp[2*i+1]=min(dp[2*i+2]+q*(eu[i]/eu[i+1]),dp[2*i]+p);
}
printf("%lld\n",x>=y?dp[0]:dp[1]);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |