Submission #415902

#	Time	Username	Problem	Language	Result	Execution time	Memory
415902		meatrow	Group Photo (JOI21_ho_t3)	C++17	100 / 100	1031 ms	263380 KiB

Main

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1e9 + 7;

ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

const int N = 5005;

int dist[N][N];
int nxt[N][N], prv[N][N];
int dp[N];
int a[N], pos[N];

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pos[j] > pos[i]) {
                nxt[i][j] = 1;
            }
            if (pos[j] < pos[i]) {
                prv[i][j] = 1;
            }
        }
        for (int j = 1; j <= n; j++) {
            nxt[i][j] += nxt[i][j - 1];
            prv[i][j] += prv[i][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        dist[i][i] = prv[i][n] - prv[i][i];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dist[i][j] = dist[i][j - 1] + (prv[j][n] - prv[j][i - 1]) - (nxt[j][j - 1] - nxt[j][i - 1]);
        }
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + dist[j + 1][i]);
        }
    }

    cout << dp[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

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