// yukicoder: No.555 世界史のレポート // 2019.7.13 bal4u #include #define HASHSIZ 900007 typedef struct { int r, w, c; } HASH; HASH hash[HASHSIZ+5], *hashend = hash + HASHSIZ; int insert(int r, int w, int c) { HASH *p = hash + (int)((((long long)r << 16) + w) % HASHSIZ); while (p->r) { if (p->r == r && p->w == w) { if (p->c <= c) return 0; p->c = c; return 1; } if (++p == hashend) p = hash; } p->r = r, p->w = w, p->c = c; return 1; } typedef struct { int r, w, c; } Q; // レポートの文字数、クリップボードの文字数、コスト Q q[1000000]; int top, end; int C, V, N; int main() { int r, w, c, mi; scanf("%d%d%d", &N, &C, &V); mi = 0x7ffffff; q[0].r = 1, q[0].w = 1, q[0].c = C, end = 1; while (top != end) { r = q[top].r, w = q[top].w, c = q[top++].c; if (r >= N) { if (c < mi) mi = c; continue; } if (c >= mi) continue; if (insert(r, w, c)) { q[end].r = r+w, q[end].w = w, q[end++].c = c + V; // paste q[end].r = r+r, q[end].w = r, q[end++].c = c + C + V; // copy & paste } } printf("%d\n", mi); return 0; }