Submission #1354989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354989		Aviansh	Developer (BOI25_dev)	C++20	0 / 100	238 ms	589824 KiB

Main

#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int arr[n];
    int mxa = 0;
    for(int &i : arr){
        cin >> i;
        mxa=max(mxa,i);
    }
    mxa+=3;
    int dp[n][mxa][2];
    for(int i = 0;i<mxa;i++){
        dp[0][i][0]=dp[0][i][1]=abs(i-arr[0]);
    }
    for(int i = 1;i<n;i++){
        for(int h = 0;h<mxa;h++){
            dp[i][h][0]=1e9;
            dp[i][h][1]=1e9;
            for(int H = 0;H<h;H++){
                dp[i][h][1]=min(dp[i][h][1],dp[i-1][H][0]);
            }
            for(int H = h+1;H<mxa;H++){
                dp[i][h][0]=min(dp[i][h][0],dp[i-1][H][1]);
            }
            dp[i][h][0]+=abs(arr[i]-h);
            dp[i][h][1]+=abs(arr[i]-h);
        }
    }
    int ans = 1e9;
    for(int i = 0;i<mxa;i++){
        ans=min({dp[n-1][i][0],dp[n-1][i][1],ans});
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 4
• Subtask 3: 0 / 13
• Subtask 4: 0 / 8
• Subtask 5: 0 / 19
• Subtask 6: 0 / 29
• Subtask 7: 0 / 27