Submission #27205

#TimeUsernameProblemLanguageResultExecution timeMemory
27205TAMREFMin-cost GCD (GA9_mcg)C++11
14 / 100
786 ms32768 KiB
#include <bits/stdc++.h> #define va first #define vb second #define mp make_pair using namespace std; typedef long long ll; typedef pair<ll,ll> pll; map<pll,int> m; pll x[100005]; ll s[100005], t[100005]; int idx; int rec(pll p){ if(!p.va||!p.vb) return 0; if(m[p]) return m[p]; ll x=p.va,y=p.vb; return m[p]=min(rec(mp(y,x%y))+s[idx],rec(x>=y?mp(x-y,y):mp(x,y-x))+t[idx]); } int main(){ int T; scanf("%d",&T); for(idx=0;idx<T;idx++){ scanf("%lld%lld%lld%lld",&x[idx].va,&x[idx].vb,&s[idx],&t[idx]); } if(*min_element(s,s+T)==*max_element(s,s+T) && *min_element(t,t+T)==*max_element(t,t+T)) for(idx=0;idx<T;idx++) printf("%d\n",rec(x[idx])); else{ for(idx=0;idx<T;idx++){ m.clear(); printf("%d\n",rec(x[idx])); } } return 0; }

Compilation message (stderr)

mcg.cpp: In function 'int main()':
mcg.cpp:19:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int T; scanf("%d",&T);
                          ^
mcg.cpp:21:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",&x[idx].va,&x[idx].vb,&s[idx],&t[idx]);
                                                                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...