Submission #1092594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092594		ortsac	Group Photo (JOI21_ho_t3)	C++17	100 / 100	1893 ms	604 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;
const int INF = 0x3f3f3f3f;

struct SegTree {
    int seg[4*MAXN];
    void build(int node, int l, int r) {
        if (l == r) {
            seg[node] = 0;
            return;
        }
        int m = (l+r)/2;
        build(2*node, l, m);
        build(2*node + 1, m + 1, r);
        seg[node] = (seg[2*node] + seg[2*node + 1]);
    }
    int query(int node, int l, int r, int tl, int tr) {
        if ((r < tl) || (tr < l)) return 0;
        if ((tl <= l) && (r <= tr)) return seg[node];
        int m = (l + r)/2;
        return (query(2*node, l, m, tl, tr) + query(2*node + 1, m + 1, r, tl, tr));
    }
    void update(int node, int l, int r, int po, int val) {
        if (l == r) {
            seg[node] = val;
            return;
        }
        int m = (l + r)/2;
        if (po <= m) update(2*node, l, m, po, val);
        else update(2*node + 1, m + 1, r, po, val);
        seg[node] = (seg[2*node] + seg[2*node + 1]);
    }
};

SegTree seg;
int dp[MAXN];

int32_t main() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int k = 1; k <= n; k++) {
        dp[k] = INF;
        vector<int> nv, po(k + 1);
        for (int i = 1; i <= n; i++) {
            if (v[i] <= k) {
                nv.push_back(v[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            po[nv[i]] = (i + 1);
        }
        seg.build(1, 1, k);
        int calc = 0;
        for (int i = k; i >= 1; i--) {
            calc += (k - po[i]);
            calc -= seg.query(1, 1, k, 1, po[i]);
            seg.update(1, 1, k, po[i], 1);
            dp[k] = min(dp[k], dp[i - 1] + calc);
        }
    }
    cout << dp[n] << "\n";
}

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