Submission #1111259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111259		borisAngelov	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5048 ms	508 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 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 bit;

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;

        for (int to = num; to <= n; ++to)
        {
            vector<int> toClear;

            for (int j = to + 1; j <= n; ++j)
            {
                bit.update(positions[j], +1);
                toClear.push_back(positions[j]);
            }

            for (int i = num; i <= to; ++i)
            {
                toRem[i] = bit.query(positions[i] - 1);
            }

            for (auto pos : toClear)
            {
                bit.update(pos, -1);
            }

            toClear.clear();

            int cost = 0, inv = 0;
            vector<pair<int, int>> actualPos;

            for (int i = num; i <= to; ++i)
            {
                int newPos = positions[i] - toRem[i];
                //cout << "here for " << i << " -> " << newPos << endl;
                actualPos.push_back({newPos, i});
            }

            sort(actualPos.begin(), actualPos.end(), greater<pair<int, int>>());

            for (int i = 0; i < actualPos.size(); ++i)
            {
                cost += abs((to - i) - actualPos[i].first);
            }

            for (int i = 0; i < actualPos.size(); ++i)
            {
                inv += bit.query(actualPos[i].second - 1);
                bit.update(actualPos[i].second, +1);
                toClear.push_back(actualPos[i].second);
            }

            for (auto pos : toClear)
            {
                bit.update(pos, -1);
            }

            int cntNums = to - num + 1;

            cost += (cntNums * (cntNums - 1)) / 2 - inv;

            //cout << num << " " << to << " :: " << cost << endl;

            dp[num] = min(dp[num], cost + dp[to + 1]);
        }

        //cout << num << " ::: " << dp[num] << endl;
    }

    cout << dp[1] << endl;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (int i = 0; i < actualPos.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int i = 0; i < actualPos.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~~

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