結果
問題 | No.2673 A present from B |
ユーザー | hirakuuuu |
提出日時 | 2024-03-15 22:00:09 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 597 ms / 2,000 ms |
コード長 | 1,441 bytes |
コンパイル時間 | 3,092 ms |
コンパイル使用メモリ | 251,160 KB |
実行使用メモリ | 6,676 KB |
最終ジャッジ日時 | 2024-03-15 22:00:30 |
合計ジャッジ時間 | 7,090 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 4 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 569 ms
6,676 KB |
testcase_07 | AC | 597 ms
6,676 KB |
testcase_08 | AC | 567 ms
6,676 KB |
testcase_09 | AC | 2 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 2 ms
6,676 KB |
testcase_12 | AC | 135 ms
6,676 KB |
testcase_13 | AC | 55 ms
6,676 KB |
testcase_14 | AC | 201 ms
6,676 KB |
testcase_15 | AC | 44 ms
6,676 KB |
testcase_16 | AC | 40 ms
6,676 KB |
testcase_17 | AC | 10 ms
6,676 KB |
testcase_18 | AC | 48 ms
6,676 KB |
testcase_19 | AC | 5 ms
6,676 KB |
testcase_20 | AC | 169 ms
6,676 KB |
testcase_21 | AC | 365 ms
6,676 KB |
testcase_22 | AC | 2 ms
6,676 KB |
testcase_23 | AC | 2 ms
6,676 KB |
testcase_24 | AC | 2 ms
6,676 KB |
testcase_25 | AC | 2 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, a, n) for(int i = a; i < n; i++) #define rrep(i, a, n) for(int i = a; i >= n; i--) #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> // constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; constexpr int IINF = 1001001001; constexpr ll INF = 1LL<<60; template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} int main(){ int n, m; cin >> n >> m; vector<int> a(m+1); rep(i, 1, m+1) cin >> a[i]; rep(i, 2, n+1){ vector<vector<int>> dp(m+1, vector<int>(n+1, IINF)); rep(j, 1, n+1) dp[0][j] = abs(i-j); rep(j, 1, m+1){ rep(k, 1, n+1){ if(k != a[j] && k != a[j]+1){ chmin(dp[j][k], dp[j-1][k]); }else if(k == a[j]){ chmin(dp[j][k], dp[j-1][k+1]); }else{ chmin(dp[j][k], dp[j-1][k-1]); } } int mi = dp[j][1]; rep(k, 2, n+1){ mi++; chmin(dp[j][k], mi); chmin(mi, dp[j][k]); } mi = dp[j][n]; rrep(k, n, 1){ mi++; chmin(dp[j][k], mi); chmin(mi, dp[j][k]); } } cout << dp[m][1] << ' '; } cout << endl; return 0; }