제출 #1208506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208506		dima2101	Group Photo (JOI21_ho_t3)	C++20	100 / 100	1640 ms	600 KiB

Main

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long

struct Fenwick
{
    int n;
    std::vector<int> t;

    Fenwick(int n) : n(n)
    {
        t.resize(n + 1);
    }
    void upd(int i, int x)
    {
        for (i; i <= n; i += (i & (-i)))
        {
            t[i] += x;
        }
    }
    int sum(int i)
    {
        int ans = 0;
        for (i; i > 0; i -= (i & (-i)))
        {
            ans += t[i];
        }
        return ans;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    std::cin >> n;

    std::vector<int> pos(n + 1);
    for (int i = 0; i < n; i++)
    {
        int x;
        std::cin >> x;
        pos[x] = i + 1;
    }

    std::vector<int> dp(n + 1, 1e18);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        Fenwick t1(n);
        Fenwick t2(n);
        // std::cout << "jdhf" << std::endl;
        for (int j = 1; j < i; j++)
        {
            t1.upd(pos[j], 1);
        }
        // std::cout << "djf" << std::endl;
        t2.upd(pos[i], 1);
        int cnt1 = t1.sum(pos[i], n);
        int cnt2 = 0;

        for (int j = i - 1; j >= 0; j--)
        {
            // std::cout << i << ' ' << j << ' ' << cnt1 << ' ' << cnt2 << ' ' << dp[j] << std::endl;
            dp[i] = std::min(dp[i], dp[j] + cnt1 + ((i - j - 1) * (i - j)) / 2 - cnt2);
            if (j != 0)
            {

                t1.upd(pos[j], -1);
                cnt1 += t1.sum(pos[j], n);
                cnt1 -= t2.sum(1, pos[j]);
                cnt2 += t2.sum(1, pos[j]);

                t2.upd(pos[j], 1);
            }
        }
        // std::cout << dp[i] << std::endl;
    }
    std::cout << dp[n];
}

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