Submission #956595

#	Time	Username	Problem	Language	Result	Execution time	Memory
956595		peterandvoi	Group Photo (JOI21_ho_t3)	C++17	100 / 100	543 ms	134736 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5005;

int n;
int h[N];
int pos[N];
int t[N];
int dp[N];
int cnt[N][N];
int cost[N][N];

int get(int l, int r) {
    return l <= r ? t[r] - t[l - 1] : 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        pos[h[i]] = i;
    }
    for (int l = n; l >= 1; --l) {
        for (int r = l + 1; r <= n; ++r) {
            cnt[l][r] = cnt[l + 1][r] + cnt[l][r - 1] - cnt[l + 1][r - 1] + (pos[l] < pos[r]);
        }
    }
    for (int r = 1; r <= n; ++r) {
        fill(t + 1, t + n + 1, 0);
        for (int i = r + 1; i <= n; ++i) {
            t[pos[i]]++;
        }
        for (int i = 1; i <= n; ++i) {
            t[i] += t[i - 1];
        }
        for (int l = r; l >= 1; --l) {
            cost[l][r] = get(1, pos[l] - 1);
            cost[l][r] += cost[l + 1][r];
        }
        for (int l = 1; l <= r; ++l) {
            cost[l][r] += cnt[l][r];
        }
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1e9;
        for (int j = 0; j < i; ++j) {
            dp[i] = min(dp[i], dp[j] + cost[j + 1][i]);
        }
    }
    cout << dp[n];
}

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