Submission #1194168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194168		VMaksimoski008	Group Photo (JOI21_ho_t3)	C++20	100 / 100	439 ms	98392 KiB

Main

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

struct fenwick {
    int n;
    vector<int> tree;

    fenwick(int _n) : n(_n+10), tree(n+50) {}

    void update(int p) {
        for(p++; p<n; p+=p&-p) tree[p]++;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }
};

signed main() {
    int n; cin >> n;
    vector<int> a(n+1), dp(n+1, 1e8), pos(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) pos[a[i]] = i;

    int cost[n+1][n+1];
    memset(cost, 0, sizeof(cost));

    fenwick fwt(n);
    for(int l=1; l<=n; l++) {
        fenwick fwt2(n);
        for(int r=l; r<=n; r++) {
            cost[l][r] = cost[l][r-1];
            cost[l][r] += fwt.query(n) - fwt.query(pos[r]);
            cost[l][r] += fwt2.query(pos[r]);
            fwt2.update(pos[r]);
        }
        fwt.update(pos[l]);
    }

    dp[0] = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            dp[i] = min(dp[i], dp[j-1] + cost[j][i]);
    cout << dp[n] << '\n';
}

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