Submission #1036475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036475		aymanrs	Giraffes (JOI22_giraffes)	C++17	59 / 100	469 ms	1048576 KiB

giraffes

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;cin >> n;
    int p[n];for(int i = 0;i < n;i++) {
        cin >> p[i];
        p[i]--;
    }
    int dp[n+1][n+1][n+1];
    for(int i = 0;i <= n;i++){
        for(int j = 0;j <= n;j++) dp[i][n-i][j] = 0;
    }
    for(int su = n-1;su >= 0;su--){
        for(int i = 0;i <= su;i++){
            int j = su-i;
            int vj = n-j-1;
            for(int k = 0;k < n;k++){
                dp[i][j][k] = min({
                    dp[i+1][j][k+1] + (p[k] != i),
                    dp[i+1][j][k] + (p[k+(n-i-j)-1] != i),
                    dp[i][j+1][k+1] + (p[k] != vj),
                    dp[i][j+1][k] + (p[k+(n-i-j)-1] != vj)
                });
            }
        }
    }
    cout << dp[0][0][0] << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 41