結果
問題 |
No.1077 Noelちゃんと星々4
|
ユーザー |
![]() |
提出日時 | 2024-12-06 00:35:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 841 bytes |
コンパイル時間 | 1,758 ms |
コンパイル使用メモリ | 170,452 KB |
実行使用メモリ | 49,152 KB |
最終ジャッジ日時 | 2024-12-06 00:36:45 |
合計ジャッジ時間 | 60,412 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 TLE * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int Y_MAX = 10000; int main(){ int N; cin >> N; vector<int> Y(N+1); for(int i=1;i<=N;i++){ cin >> Y[i]; } vector<vector<int>> dp(N+1,vector<int>(Y_MAX+1)); for(int i=0;i<=Y_MAX;i++){ dp[1][i] = abs(Y[1]-i); } int min; for(int n=2;n<=N;n++){ for(int y=0;y<=Y_MAX;y++){ //dp[n][y]求めるよ min = 998244353; for(int y_0=0;y_0<=y;y_0++){ if(min > dp[n-1][y_0]){ min = dp[n-1][y_0]; } } dp[n][y] = min + abs(Y[n]-y); } } int min_result = 998244353; for(int y=0;y<=Y_MAX;y++){ if(min_result > dp[N][y]){ min_result = dp[N][y]; } } cout << min_result << endl; }