Submission #1355097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355097		Aviansh	Developer (BOI25_dev)	C++20	54 / 100	2097 ms	150284 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];
    for(int &i : arr){
        cin >> i;
    }
    auto fin = [&] (int i){
        unordered_set<int>s;
        for(int j = i-4;j<=i+4;j++){
            if(j>=0&&j<n){
                s.insert(arr[j]);
                s.insert(arr[j]+1);
                s.insert(arr[j]-1);
            }
        }
        return s;
    };
    map<int,array<long long,2>> dp[n];
    for(int i : fin(0)){
        dp[0][i][0]=dp[0][i][1]=abs(i-arr[0]);
    }
    for(int i = 1;i<n;i++){
        auto x = fin(i);
        for(int h : x){
            dp[i][h][0]=1e18;
            dp[i][h][1]=1e18;
            auto y = fin(i-1);
            for(int H : y){
                if(H<h){
                    dp[i][h][1]=min(dp[i][h][1],dp[i-1][H][0]);
                }
                else if(H>h){
                    dp[i][h][0]=min(dp[i][h][0],dp[i-1][H][1]);
                }
                else{
                    dp[i][h][0]=min(dp[i][h][0],dp[i-1][H][0]);
                    dp[i][h][1]=min(dp[i][h][1],dp[i-1][H][1]);
                }
            }
            dp[i][h][0]+=abs(arr[i]-h);
            dp[i][h][1]+=abs(arr[i]-h);
        }
    }
    long long ans = 1e18;
    for(int i : fin(n-1)){
        ans=min({dp[n-1][i][0],dp[n-1][i][1],ans});
    }
    cout << ans;
    return 0;
}

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