結果

問題 No.1077 Noelちゃんと星々4
コンテスト
ユーザー rieaaddlreiuu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0