Submission #439346

#	Time	Username	Problem	Language	Result	Execution time	Memory
439346		vkgainz	Group Photo (JOI21_ho_t3)	C++17	100 / 100	384 ms	196528 KiB

Main

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

int main() {
    int N; cin >> N;
    vector<int> H(N);
    vector<int> P(N);
    for(int i = 0; i < N; i++) {
        cin >> H[i];
        --H[i];
        P[H[i]] = i;
    }
    vector<int> dp(N + 1);
    vector<vector<int>> l(N, vector<int>(N));
    for(int j = 0; j < N; j++) {
        for(int i = 0; i < j; i++) {
            if(i > 0) l[i][j] = l[i - 1][j];
            l[i][j] += (P[i] > P[j]);
        }
    }
    vector<vector<int>> inv(N, vector<int>(N));
    for(int len = 2; len <= N; len++) {
        for(int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            inv[i][j] = inv[i][j - 1] + inv[i + 1][j] - inv[i + 1][j - 1] + (P[i] < P[j]);
        }
    }
    for(int i = N - 1; i >= 0; i--) {
        dp[i] = 1000000000;
        int sum = 0;
        for(int j = i; j < N; j++) {
            sum += P[j];
            if(i > 0) sum += l[i - 1][j];
            int cost = sum + inv[i][j] - (i + j) * (j - i + 1) / 2;
            dp[i] = min(dp[i], dp[j + 1] + cost);
        }
    }
    cout << dp[0];
}

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