Submission #12812

#TimeUsernameProblemLanguageResultExecution timeMemory
12812paulsohnMin-cost GCD (GA9_mcg)C++98
30 / 100
123 ms1108 KiB
#include<stdio.h> #define min(a,b) (a<b?a:b) const long long INF = 5123456789012345678LL; long long a, b, p, q, Q[1000], DP[1000][2]; int T, cost; int main(){ int x, y, r; int i, s; scanf("%d", &T); while(T--){ scanf("%lld %lld %lld %lld", &a, &b, &p, &q); x=(a>b?a:b); y=(a>b?b:a); i=0; do{ r=x%y; Q[i]=x/y; x=y; y=r; i++; }while(r); s=i; if(a>=b){ DP[0][0]=0; DP[0][1]=INF; } else{ DP[0][0]=p; DP[0][1]=0; } for(i=0; i<s; i++){ DP[i+1][0]=min(DP[i][0]+p, DP[i][1]+Q[i]*q); DP[i+1][1]=DP[i][0]+Q[i]*q; } printf("%lld\n", min(DP[s][0], DP[s][1])); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...