Submission #1111258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111258		borisAngelov	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5052 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];

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)
        {
            for (int i = 1; i <= n; ++i)
            {
                toRem[i] = 0;
            }

            for (int i = num; i <= to; ++i)
            {
                for (int j = positions[i] - 1; j >= 1; --j)
                {
                    if (a[j] > to) ++toRem[i];
                }
            }

            int cost = 0, inv = 0;
            vector<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);
            }

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

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

            for (int i = num; i <= to; ++i)
            {
                for (int j = i - 1; j >= num; --j)
                {
                    if (positions[j] > positions[i])
                    {
                        ++inv;
                    }
                }
            }

            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:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             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