結果
問題 | No.1478 Simple Sugoroku |
ユーザー |
|
提出日時 | 2021-03-06 02:05:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 1,189 bytes |
コンパイル時間 | 1,990 ms |
コンパイル使用メモリ | 195,632 KB |
最終ジャッジ日時 | 2025-01-19 12:16:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
/** * author: otera * created: 06.03.2021 01:14:21 **/ #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } void solve() { int n, m; cin >> n >> m; vector<ll> b(m); vector<ll> sum(m + 1, 0); for(int i = 0; i < m; ++ i) { cin >> b[i]; } for(int i = 0; i < m; ++ i) { sum[i + 1] = sum[i] + (b[m - 1] - b[m - 1 - i]); } ld ans = (ld)(n - 1); int ok = m - 1, ng = 0; auto check = [&](int x) -> bool { int right = b[m - 1] - b[x]; ld left = ((ld)m + (ld)sum[m - x]) / (ld)(m - x); if((ld)left >= (ld)right) return true; else return false; }; while(ok - ng > 1) { int mid = (ok + ng) / 2; if(check(mid)) ok = mid; else ng = mid; } ld q = ((ld)m + (ld)sum[m - ok]) / (ld)(m - ok); chmin(ans, (ld)(n - b[m - 1] + b[0] - 1) + q); cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); // INT(t); rep(i, t)solve(); solve(); return 0; }