結果
問題 | No.2890 Chiffon |
ユーザー | tnakao0123 |
提出日時 | 2024-09-15 15:47:48 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,185 bytes |
コンパイル時間 | 354 ms |
コンパイル使用メモリ | 44,668 KB |
実行使用メモリ | 6,976 KB |
最終ジャッジ日時 | 2024-09-26 14:42:46 |
合計ジャッジ時間 | 2,457 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
/* -*- coding: utf-8 -*- * * 2890.cc: No.2890 Chiffon - yukicoder */ #include<cstdio> #include<algorithm> using namespace std; /* constant */ const int MAX_K = 500000; const int MAX_K2 = MAX_K * 2; /* typedef */ /* global variables */ int as[MAX_K2 + 1]; /* subroutines */ bool check(int n, int k, int mini, int w) { for (int st = as[mini] + 1; st <= as[mini + 1]; st++) { bool ok = true; int x = st; for (int i = mini + 1; ok && i <= mini + k; i++) { x = max(x + w, as[i] + 1); ok = (x <= as[i + 1]); } if (ok && x <= st + n) return true; } return false; } /* main */ int main() { int n, k; scanf("%d%d", &n, &k); int k2 = k * 2; for (int i = 0; i < k; i++) { scanf("%d", as + i); as[i] /= 2; as[k + i] = as[i] + n; } as[k2] = as[k] + n; int mind = as[1] - as[0], mini = 0; for (int i = 1; i < k; i++) if (mind > as[i + 1] - as[i]) mind = as[i + 1] - as[i], mini = i; //printf(" mind=%d, mini=%d\n", mind, mini); int w0 = 1, w1 = n; while (w0 + 1 < w1) { int w = (w0 + w1) / 2; if (check(n, k, mini, w)) w0 = w; else w1 = w; } printf("%d\n", w0 * 2); return 0; }