Submission #622983

#	Time	Username	Problem	Language	Result	Execution time	Memory
622983		elkernos	Group Photo (JOI21_ho_t3)	C++17	100 / 100	424 ms	196444 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> p(n + 1), pr(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        pr[p[i]] = i;
    }
    vector inv(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            inv[i][j] = inv[i][j - 1] + inv[i - 1][j] - inv[i - 1][j - 1] + (i < j && pr[j] < pr[i]); // j i
        }
    }
    auto c = [&](int l, int r) {
        return (inv[r][r] - inv[l - 1][r] - inv[r][l - 1] + inv[l - 1][l - 1]);
    };
    auto C2 = [&](int x) {
        return x * (x - 1) / 2;
    };
    const int oo = 1e18;
    vector<int> dp(n + 1, oo);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        dp[i] = C2(i) - c(1, i);
        for(int j = 1; j <= i; j++) {
            int one = C2(i - j + 1) - c(j, i);
            int two = c(1, i) - (j == 1 ? 0 : c(1, j - 1)) - c(j, i);
            dp[i] = min(dp[i], dp[j - 1] + one + two);
        }
    }
    cout << dp[n] << '\n';
}

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