Submission #1114163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114163		borisAngelov	Group Photo (JOI21_ho_t3)	C++17	100 / 100	323 ms	832 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5005;
const int inf = 1e9;

int n;
int a[maxn], positions[maxn], toRem[maxn];

int dp[maxn];

struct FenwickTree
{
    int tree[maxn];

    void reset(int MAX)
    {
        fill(tree, tree + MAX + 1, 0);
    }

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

    int query(int pos)
    {
        int result = 0;

        for (; pos >= 1; pos -= (pos & (-pos)))
        {
            result += tree[pos];
        }

        return result;
    }
};

FenwickTree treeActive;
FenwickTree treeSmaller;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

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

    dp[n + 1] = 0;

    for (int num = n; num >= 1; --num)
    {
        dp[num] = inf;

        treeActive.update(positions[num], +1);
        treeSmaller.reset(n);

        int cost = 0;

        for (int to = num; to <= n; ++to)
        {
            cost += treeActive.query(positions[to]) - 1;
            treeSmaller.update(positions[to], +1);
            cost -= treeSmaller.query(n) - treeSmaller.query(positions[to]);
            dp[num] = min(dp[num], cost + dp[to + 1]);
        }
    }

    cout << dp[1] << endl;

    return 0;
}

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