Submission #27205

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
27205	2017-07-10 13:19:52	TAMREF	Min-cost GCD (GA9_mcg)	C++11	14 / 100	786 ms	32768 KiB

mcg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]));
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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]);
                                                                        ^

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