Submission #1355109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355109		Aviansh	Developer (BOI25_dev)	C++20	54 / 100	2109 ms	524816 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;
    }
    set<int>mem[n];
    auto fin = [&] (int i){
        for(int j = i-4;j<=i+4;j++){
            if(j>=0&&j<n){
                mem[i].insert(arr[j]);
                mem[i].insert(arr[j]+1);
                mem[i].insert(arr[j]-1);
            }
        }
    };
    unordered_map<int,array<long long,2>> dp[n];
    fin(0);
    for(int i : mem[0]){
        dp[0][i][0]=dp[0][i][1]=abs(i-arr[0]);
    }
    for(int i = 1;i<n;i++){
        fin(i);
        for(int h : mem[i]){
            dp[i][h][0]=1e18;
            dp[i][h][1]=1e18;;
            for(int H : mem[i-1]){
                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 : mem[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