結果
問題 | 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;}