Submission #1214023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214023		minhpk	Group Photo (JOI21_ho_t3)	C++20	100 / 100	226 ms	98552 KiB

Main

#include <bits/stdc++.h>
using namespace std;

static const int INF = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> z(N), pos(N);
    for (int i = 0; i < N; i++) {
        cin >> z[i];
        z[i]--;
    }
    for (int i = 0; i < N; i++) {
        pos[z[i]] = i;
    }

    int pre[5005][5006];
    for (int v = 0; v <= N; v++) {
        pre[N - 1][v] = 0;
    }
    for (int p = N - 1; p > 0; p--) {
        int val = z[p];
        for (int v = 0; v <= val; v++) {
            pre[p - 1][v] = pre[p][v] + 1;
        }
        for (int v = val + 1; v <= N; v++) {
            pre[p - 1][v] = pre[p][v];
        }
    }

    vector<int> dp(N + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
        long long tmp = 0;
        for (int j = i - 1; j >= 0; j--) {
            tmp += (N - i) + pre[pos[j]][j] - 2 * pre[pos[j]][i];
            dp[i] = min(dp[i], dp[j] + (int)tmp);
        }
    }

    cout << dp[N] << "\n";
    return 0;
}

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