Submission #935069

#	Time	Username	Problem	Language	Result	Execution time	Memory
935069		haxorman	Group Photo (JOI21_ho_t3)	C++14	100 / 100	254 ms	197008 KiB

Main

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

#define int long long

const int mxN = 5007;

int arr[mxN], pos[mxN], inv[mxN][mxN], dp[mxN];

int f(int h) {
    if (!h) {
        return 0;
    }

    if (dp[h] != -1) {
        return dp[h];
    }
    
    int ret = INT_MAX, add = 0;
    for (int x = h; x >= 1; --x) {
        add += h - pos[x] + 2*inv[x][h] - inv[x][x];
        ret = min(ret, f(x-1) + add);
    }
    return dp[h] = ret;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        pos[arr[i]] = i;
    }

    for (int y = 1; y <= n; ++y) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (arr[i] > y) {
                ++cnt;
            }
            inv[arr[i]][y] = cnt;
        }
    }

    memset(dp, -1, sizeof(dp));
    cout << f(n) << "\n";
}

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