結果
問題 | No.2039 Copy and Avoid |
ユーザー |
![]() |
提出日時 | 2022-08-17 01:33:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,345 bytes |
コンパイル時間 | 461 ms |
コンパイル使用メモリ | 46,020 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-03 20:34:19 |
合計ジャッジ時間 | 1,557 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
/* -*- coding: utf-8 -*-** 2039.cc: No.2039 Copy and Avoid - yukicoder*/#include<cstdio>#include<algorithm>using namespace std;/* constant */const int MAX_M = 5000;const int MAX_K = 1344;const long long LINF = 1LL << 62;/* typedef */typedef long long ll;/* global variables */int cs[MAX_M], ds[MAX_K];ll dp[MAX_K];/* subroutines */inline void setmin(ll &a, ll b) { if (a > b) a = b; }/* main */int main() {int n, m, a, b;scanf("%d%d%d%d", &n, &m, &a, &b);for (int i = 0; i < m; i++) scanf("%d", cs + i);sort(cs, cs + m);int k = 0;for (int p = 1; p * p <= n; p++)if (n % p == 0) {ds[k++] = p;int q = n / p;if (q != p) ds[k++] = q;}sort(ds, ds + k);//for (int i = 0; i < k; i++) printf("%d ", ds[i]); putchar('\n');fill(dp, dp + k, LINF);dp[0] = 0;for (int i = 0; i < k; i++) {if (dp[i] >= LINF) continue;int di = ds[i];int x = lower_bound(cs, cs + m, di) - cs;for (; x < m && cs[x] % di != 0; x++);int maxj = (x >= m) ? k : lower_bound(ds, ds + k, cs[x]) - ds;//printf("ds[%d]=%d, maxj=%d\n", i, di, maxj);for (int j = i + 1; j < maxj; j++)if (ds[j] % di == 0)setmin(dp[j], dp[i] + ((ll)a * (ds[j] / di - 1) + b));}printf("%lld\n", (dp[k - 1] < LINF) ? dp[k - 1] - b : -1LL);return 0;}