Submission #1274774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274774		MisterReaper	Group Photo (JOI21_ho_t3)	C++20	100 / 100	299 ms	196600 KiB

Main

// File groupphoto.cpp created on 30.09.2025 at 19:37:11
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

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

    int N;
    std::cin >> N;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        --A[i];
    }

    std::vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        p[A[i]] = i;
    }

    std::vector<int> s(N);
    std::vector<std::vector<int>> g(N, std::vector<int>(N));
    std::vector<std::vector<int>> h(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = A[i]; j < N; ++j) {
            s[j]++;
        }
        for (int j = A[i]; j < N; ++j) {
            g[A[i]][j] = s[N - 1] - s[j];
            h[A[i]][j] = (j - A[i]) - (s[j] - s[A[i]]);
        }
    }

    std::vector<int> f(N + 1, N * N);
    f[0] = 0;
    for (int i = 0; i < N; ++i) {
        int cost = 0;
        for (int j = i; j >= 0; --j) {
            cost += g[j][i] + h[j][i];
            f[i + 1] = std::min(f[i + 1], f[j] + cost);
        }
    }

    debug(f);

    std::cout << f[N] << '\n';

    return 0;
}

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