Submission #625119

#	Time	Username	Problem	Language	Result	Execution time	Memory
625119		boris_mihov	Group Photo (JOI21_ho_t3)	C++14	100 / 100	418 ms	588 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 5000 + 10;
const int INF  = 1e9;

int dp[MAXN];
int treePos[MAXN];
int treeSmaller[MAXN];
int a[MAXN], n;
int pos[MAXN];

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

int query(int tree[], int pos)
{
    int sum = 0;
    for (int i = pos ; i >= 1 ; i -= i & (-i))
    {
        sum += tree[i];
    }

    return sum;
}

void solve()
{
    dp[n+1] = 0;
    for (int from = n ; from >= 1 ; --from)
    {
        std::fill(treeSmaller + 1, treeSmaller + 1 + n, 0);
        update(treePos, pos[from], 1);
        dp[from] = INF;
        int add = 0;

        for (int next = from ; next <= n ; ++next)
        {
            update(treeSmaller, pos[next], 1);
            add += query(treePos, pos[next]) - 1;
            add -= query(treeSmaller, n) - query(treeSmaller, pos[next]);
            dp[from] = std::min(dp[from], dp[next + 1] + add);
        }
    }

    std::cout << dp[1] << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
        pos[a[i]] = i;
    }
}

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

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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