Submission #12661

#TimeUsernameProblemLanguageResultExecution timeMemory
12661dohyun0324Min-cost GCD (GA9_mcg)C++98
100 / 100
306 ms1084 KiB
#include<stdio.h> #define M 922337203685477580LL int t,w; long long x,y,p,q,dap; struct data { long long x,y; }a[101]; struct data2 { long long mi,ma; }d[101]; void gcd(long long x,long long y) { w++; a[w].x=x; a[w].y=y; if(x%y==0) return; gcd(y,x%y); } int main() { int i,j; scanf("%d",&t); for(i=1;i<=t;i++) { dap=M; w=0; for(j=1;j<=100;j++) d[j].ma=M, d[j].mi=M; scanf("%lld %lld %lld %lld",&x,&y,&p,&q); if(x==y){ if(p>q) printf("%lld\n",q); else printf("%lld\n",p); continue; } if(x>y) gcd(x,y); else gcd(y,x); if(x>y) d[1].ma=0; else d[1].mi=0, d[1].ma=p; for(j=2;j<=w;j++) { if(q<=p*100/(a[j-1].x/a[j-1].y+1)+1 && d[j].mi>d[j-1].ma+q*(a[j-1].x/a[j-1].y)) d[j].mi=d[j-1].ma+q*(a[j-1].x/a[j-1].y); if(d[j].ma>d[j-1].ma+p) d[j].ma=d[j-1].ma+p; if(q<=p*100/(a[j-1].x/a[j-1].y+1)+1 && d[j].ma>d[j-1].mi+q*(a[j-1].x/a[j-1].y)) d[j].ma=d[j-1].mi+q*(a[j-1].x/a[j-1].y); if(d[j].ma>d[j].mi+p) d[j].ma=d[j].mi+p; } if(q<=p*100/(a[w].x/a[w].y+1)+1 && dap>d[w].mi+q*(a[w].x/a[w].y)) dap=d[w].mi+q*(a[w].x/a[w].y); if(q<=p*100/(a[w].x/a[w].y+1)+1 && dap>d[w].ma+q*(a[w].x/a[w].y)) dap=d[w].ma+q*(a[w].x/a[w].y); if(dap>d[w].ma+p) dap=d[w].ma+p; if(dap>d[w].mi+p+p) dap=d[w].mi+p+p; printf("%lld\n",dap); } 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...