結果
問題 | No.1782 ManyCoins |
ユーザー |
👑 |
提出日時 | 2021-12-11 23:08:36 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 25,344 KB |
最終ジャッジ日時 | 2024-07-20 06:27:35 |
合計ジャッジ時間 | 3,147 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <stdio.h> int main() { int i, N, W[21], max = 0; long long L; scanf("%d %lld", &N, &L); for (i = 1; i <= N; i++) { scanf("%d", &(W[i])); if (max < W[i]) max = W[i]; } const long long sup = 1LL << 40; int j, k, head, tail; long long ans = -1, dist[1000001], q[2000001][2], tmp; for (i = 1, dist[0] = 0, q[max][0] = 0, q[max][1] = 0; i < max; i++) dist[i] = sup; for (head = max, tail = max + 1; head < tail; head++) { i = q[head][0]; if (q[head][1] != dist[i]) continue; if (L % max >= i) tmp = L / max * max + i; else tmp = (L / max - 1) * max + i; if (tmp < dist[i] * max + i) continue; ans += (tmp - (dist[i] * max + i)) / max + 1; for (j = 1; j <= N; j++) { if (W[j] == max) continue; if (i + W[j] < max) { k = i + W[j]; if (dist[k] > dist[i]) { dist[k] = dist[i]; q[head][0] = k; q[head--][1] = dist[k]; } } else { k = i + W[j] - max; if (dist[k] > dist[i] + 1) { dist[k] = dist[i] + 1; q[tail][0] = k; q[tail++][1] = dist[k]; } } } } printf("%lld\n", ans); fflush(stdout); return 0; }