結果

問題 No.555 世界史のレポート
ユーザー alpha_virginisalpha_virginis
提出日時 2017-08-11 23:38:09
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,547 ms / 2,000 ms
コード長 2,325 bytes
コンパイル時間 1,802 ms
コンパイル使用メモリ 171,804 KB
実行使用メモリ 200,892 KB
最終ジャッジ日時 2024-04-20 23:47:57
合計ジャッジ時間 6,770 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 325 ms
53,468 KB
testcase_11 AC 215 ms
28,988 KB
testcase_12 AC 446 ms
53,564 KB
testcase_13 AC 669 ms
102,588 KB
testcase_14 AC 1,547 ms
200,892 KB
testcase_15 AC 44 ms
10,340 KB
testcase_16 AC 192 ms
28,860 KB
testcase_17 AC 61 ms
16,696 KB
testcase_18 AC 269 ms
53,560 KB
testcase_19 AC 301 ms
53,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

long modpow(long x, long n) {
   if( n == 0 ) return 1;
   long t = x * x % mod;
   return modpow(t, n / 2) * (n % 2 == 1 ? x : 1) % mod;
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   struct T {
      T(long x, long y, long c) : x(x), y(y), c(c) {}
      long x, y;
      long c;
      bool operator < (const T& t) const {
         // if( c != t.c ) return c > t.c;
         // return x < t.x;
         return c > t.c;
      }
   };
   void solve() {
      long n, c, v; scan(n, c, v);
      std::priority_queue<T> q;
      LI xs(112345, (1LL << 53));
      q.push(T(1, 0, 0));
      while( not q.empty() ) {
         T t = q.top(); q.pop();
         // if( xs[t.x+t.y] < t.c ) continue;
         // xs[t.x] = t.c;
         if( t.x >= n ) {
            printf("%ld\n", t.c);
            return;
         }
         if( t.x != t.y ) q.push(T(t.x, t.x, t.c+c));
         q.push(T(t.x+t.y, t.y, t.c+v));
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}
0