oj.uz

Submission #27205

# Submission time Handle Problem Language Result Execution time Memory
27205 2017-07-10T13:19:52 Z TAMREF Min-cost GCD (GA9_mcg) C++11
14 / 100
 786 ms 32768 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5148 KB Output is correct
2 Correct 0 ms 5148 KB Output is correct
3 Correct 0 ms 5148 KB Output is correct
4 Correct 0 ms 5148 KB Output is correct
5 Correct 0 ms 5148 KB Output is correct
6 Correct 0 ms 5148 KB Output is correct
7 Correct 0 ms 5148 KB Output is correct
8 Correct 0 ms 5148 KB Output is correct
9 Correct 0 ms 5148 KB Output is correct
10 Correct 0 ms 5148 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 786 ms 32768 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 7200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 269 ms 32768 KB Memory limit exceeded
2 Halted 0 ms 0 KB -