結果
問題 | No.2039 Copy and Avoid |
ユーザー | 👑 ygussany |
提出日時 | 2022-08-12 22:16:14 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,391 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 31,364 KB |
実行使用メモリ | 5,900 KB |
最終ジャッジ日時 | 2023-10-24 10:25:07 |
合計ジャッジ時間 | 2,330 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
5,900 KB |
testcase_01 | AC | 1 ms
4,368 KB |
testcase_02 | AC | 2 ms
4,368 KB |
testcase_03 | AC | 1 ms
4,368 KB |
testcase_04 | AC | 1 ms
4,368 KB |
testcase_05 | AC | 2 ms
4,368 KB |
testcase_06 | AC | 1 ms
4,368 KB |
testcase_07 | AC | 1 ms
4,368 KB |
testcase_08 | AC | 1 ms
4,368 KB |
testcase_09 | AC | 1 ms
4,368 KB |
testcase_10 | AC | 1 ms
4,368 KB |
testcase_11 | AC | 1 ms
4,368 KB |
testcase_12 | AC | 1 ms
4,368 KB |
testcase_13 | AC | 35 ms
5,900 KB |
testcase_14 | AC | 36 ms
5,900 KB |
testcase_15 | AC | 35 ms
5,900 KB |
testcase_16 | AC | 33 ms
5,900 KB |
testcase_17 | AC | 2 ms
4,368 KB |
testcase_18 | AC | 2 ms
4,368 KB |
testcase_19 | AC | 2 ms
4,368 KB |
testcase_20 | AC | 3 ms
4,368 KB |
testcase_21 | AC | 1 ms
4,368 KB |
testcase_22 | AC | 1 ms
4,368 KB |
testcase_23 | AC | 1 ms
4,368 KB |
testcase_24 | AC | 1 ms
4,368 KB |
testcase_25 | AC | 1 ms
4,368 KB |
testcase_26 | AC | 1 ms
4,368 KB |
testcase_27 | AC | 1 ms
4,368 KB |
testcase_28 | AC | 1 ms
4,368 KB |
testcase_29 | AC | 1 ms
4,368 KB |
testcase_30 | AC | 1 ms
4,368 KB |
ソースコード
#include <stdio.h> const long long sup = 1LL << 60; typedef struct Edge { struct Edge *next; int v; long long cost; } edge; void chmin(int* a, int b) { if (*a > b) *a = b; } int main() { int i, N, M, A, B, C[5001]; scanf("%d %d %d %d", &N, &M, &A, &B); for (i = 1; i <= M; i++) scanf("%d", &(C[i])); int n = 0, div[2001]; for (i = 1; i * i <= N; i++) { if (N % i != 0) continue; div[++n] = i; if (i * i != N) div[++n] = N / i; } int m = 0, u, w, min; edge *adj[2001] = {}, e[2000001], *p; for (u = 1; u <= n; u++) { for (i = 1, min = N + 1; i <= M; i++) if (C[i] % div[u] == 0) chmin(&min, C[i]); for (w = 1; w <= n; w++) { if (w == u || div[w] % div[u] != 0 || min <= div[w]) continue; e[m].v = w; e[m].cost = (long long)A * (div[w] / div[u] - 1) + B; e[m].next = adj[u]; adj[u] = &(e[m++]); } } int flag[2001] = {}, argmin; long long dist[2001], minll; for (u = 2, dist[1] = -B; u <= n; u++) dist[u] = sup; while (1) { for (u = 1, minll = sup; u <= n; u++) { if (flag[u] == 0 && minll > dist[u]) { minll = dist[u]; argmin = u; } } if (minll == sup) break; u = argmin; flag[u] = 1; for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (dist[w] > dist[u] + p->cost) dist[w] = dist[u] + p->cost; } } if (dist[2] == sup) printf("-1\n"); else printf("%lld\n", dist[2]); fflush(stdout); return 0; }