Submission #12097

#	Time	Username	Problem	Language	Result	Execution time	Memory
12097		ainu7	Min-cost GCD (GA9_mcg)	C++98	57 / 100	725 ms	1720 KiB

mcg

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

struct state {
  long long a, b, cost;
  state(long long _a, long long _b, long long _cost) {
    cost = _cost;
    a = _a;
    b = _b;
  };
  bool operator < (const state & another) const {
    if (cost != another.cost) return cost < another.cost;
    if (a != another.a) return a < another.a;
    return b < another.b;
  }
};

int main()
{
  int T;
  cin >> T;
  for (int i=0; i<T; i++) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    set<state> S;
    S.insert(state(a, b, 0));
    long long res = 1LL<<62;

    long long c1 = 0, c2 = 0;
    if (a > b) c2 = 1LL<<62;
    if (a < b) c1 = p, swap(a, b);

    while (b) {
      long long c = a / b;
      long long d = a % b;
      long long d1 = c1+p;
      long long d2 = 1LL<<62;
      if (1.0*c*q < (1LL<<61))
        d2 = min(d2, c1+c*q);
      if (1.0*c*q < (1LL<<61))
        d1 = min(d1, c2+c*q);

      d1 = min(d1, d2+p);

      a = b;
      b = d;
      c1 = d1;
      c2 = d2;
    }
    cout << min(c1, c2) << endl;
  }
}

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