Submission #939565

#	Time	Username	Problem	Language	Result	Execution time	Memory
939565		kitlix	Group Photo (JOI21_ho_t3)	C++17	100 / 100	710 ms	196804 KiB

Main

#include <bits/stdc++.h>

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> ind(n);
    for (int i = 0; i < n; ++i) {
        int ai;
        cin >> ai;
        --ai;
        ind[ai] = i;
    }
    vector<vector<int>> invprefsum(n, vector<int>(n)), antiinvprefsum(n, vector<int>(n));
    for (int a = 0; a < n; ++a) {
        for (int b = a + 1; b < n; ++b) {
            if (ind[b] < ind[a])
                invprefsum[a][b] = 1;
            else
                antiinvprefsum[a][b] = 1;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i) {
                invprefsum[i][j] += invprefsum[i - 1][j];
                antiinvprefsum[i][j] += antiinvprefsum[i - 1][j];
            }
            if (j) {
                invprefsum[i][j] += invprefsum[i][j - 1];
                antiinvprefsum[i][j] += antiinvprefsum[i][j - 1];
            }
            if (i && j) {
                invprefsum[i][j] -= invprefsum[i - 1][j - 1];
                antiinvprefsum[i][j] -= antiinvprefsum[i - 1][j - 1];
            }
        }
    }
    auto cinv = [&](int l1, int r1, int l2, int r2) {
        int ans = invprefsum[r1][r2];
        if (l1)
            ans -= invprefsum[l1 - 1][r2];
        if (l2)
            ans -= invprefsum[r1][l2 - 1];
        if (l1 && l2)
            ans += invprefsum[l1 - 1][l2 - 1];
        return ans;
        };
    auto cantiinv = [&](int l1, int r1, int l2, int r2) {
        int ans = antiinvprefsum[r1][r2];
        if (l1)
            ans -= antiinvprefsum[l1 - 1][r2];
        if (l2)
            ans -= antiinvprefsum[r1][l2 - 1];
        if (l1 && l2)
            ans += antiinvprefsum[l1 - 1][l2 - 1];
        return ans;
        };
    vector<int> dp(n);
    for (int i = 1; i < n; ++i) {
        dp[i] = cantiinv(0, i, 0, i);
        for (int j = i; j > 0; --j) {
            int newval = cantiinv(j, i, j, i);
            newval += dp[j - 1];
            newval += cinv(0, j - 1, j, i);
            dp[i] = min(dp[i], newval);
        }
    }
    cout << dp.back();
}

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