結果
問題 | No.2673 A present from B |
ユーザー |
|
提出日時 | 2024-03-15 21:57:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 984 bytes |
コンパイル時間 | 2,134 ms |
コンパイル使用メモリ | 200,692 KB |
最終ジャッジ日時 | 2025-02-20 05:04:49 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; vector<int> A(M); for(auto &a : A) cin >> a; reverse(A.begin(),A.end()); int inf = 1e9; vector<vector<int>> dp(M+1,vector<int>(N+2,inf)); dp.at(0).at(1) = 0; auto chmin = [](auto &a, auto b){a = min(a,b);}; for(int i=0; i<=M; i++){ for(int k=2; k<=N; k++) chmin(dp.at(i).at(k),dp.at(i).at(k-1)+1); for(int k=N-1; k>=1; k--) chmin(dp.at(i).at(k),dp.at(i).at(k+1)+1); if(i == M) break; int a = A.at(i); for(int k=1; k<=N; k++){ if(k == a) chmin(dp.at(i+1).at(k+1),dp.at(i).at(k)); else if(k == a+1) chmin(dp.at(i+1).at(k-1),dp.at(i).at(k)); else chmin(dp.at(i+1).at(k),dp.at(i).at(k)); } } for(int i=2; i<=N; i++){ if(i != 2) cout << " "; cout << dp.back().at(i); } cout << endl; }