Submission #1162581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162581		Der_Vlapos	Group Photo (JOI21_ho_t3)	C++20	100 / 100	1575 ms	612 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

struct segTree
{
    vector<int> tree;
    int sz = 0;

    void init(int n)
    {
        sz = n;
        tree.resize(2 * sz, 0);
    }

    void set(int pos, int val)
    {
        pos += sz;
        tree[pos] = val;
        pos >>= 1;
        while (pos)
        {
            tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
            pos >>= 1;
        }
    }

    int get(int l, int r)
    {
        int res = 0;
        l += sz;
        r += sz;
        while (l < r)
        {
            if (l & 1)
                res += tree[l++];
            if (r & 1)
                res += tree[--r];
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

#define int ll
const ll INF = 1e18 + 10;

struct test
{
    void solve()
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            a[i]--;
        }

        vector<int> pos(n);
        for (int i = 0; i < n; ++i)
            pos[a[i]] = i;

        vector<int> dp(n + 1, INF);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            segTree tree1, tree2;
            tree1.init(n);
            tree2.init(n);

            for (int j = i; j < n; ++j)
                tree1.set(pos[j], 1);

            int curCost = 0;
            for (int j = i - 1; j >= 0; --j)
            {
                curCost += tree1.get(0, pos[j]);
                curCost += tree2.get(pos[j], n);
                tree2.set(pos[j], 1);
                dp[i] = min(dp[i], dp[j] + curCost);
            }
        }
        cout << dp[n] << '\n';
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

Main.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~

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