Submission #1312551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312551		AMnu	Group Photo (JOI21_ho_t3)	C++20	100 / 100	265 ms	134432 KiB

Main

#include <iostream>
using namespace std;

const int MAXN = 5e3+5, INF = 1e9;

int N, A, pos[MAXN], inv[MAXN][MAXN], mov[MAXN][MAXN], dp[MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i=1;i<=N;i++) {
        cin >> A;
        pos[A] = i;
    }
    for (int i=N;i>=1;i--) {
        for (int j=i+1;j<=N;j++) {
            inv[i][j] = inv[i][j-1]+inv[i+1][j]-inv[i+1][j-1]+(pos[i]<pos[j]);
        }
    }
    for (int i=N;i>=1;i--) {
        for (int j=N;j>i;j--) {
            mov[i][j] = mov[i+1][j]+mov[i][j+1]-mov[i+1][j+1]+(pos[i]>pos[j]);
        }
    }
    for (int i=1;i<=N;i++) {
        dp[i] = INF;
        for (int j=0;j<i;j++) {
            dp[i] = min(dp[i],dp[j]+inv[j+1][i]+mov[j+1][i+1]);
        }
    }
    cout << dp[N] << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36