Submission #1222390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222390		badge881	Group Photo (JOI21_ho_t3)	C++20	100 / 100	1962 ms	640 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;
const int INF = 1e9;

struct SegTree
{
    int seg[4 * MAXN];
    void init(int node, int l, int r)
    {
        if (l == r)
        {
            seg[node] = 0;
            return;
        }
        int m = (l + r) / 2;
        init(2 * node, l, m);
        init(2 * node + 1, m + 1, r);
        seg[node] = (seg[2 * node] + seg[2 * node + 1]);
    }
    int query(int node, int l, int r, int tl, int tr)
    {
        if ((r < tl) || (tr < l))
            return 0;
        if ((tl <= l) && (r <= tr))
            return seg[node];
        int m = (l + r) / 2;
        return (query(2 * node, l, m, tl, tr) + query(2 * node + 1, m + 1, r, tl, tr));
    }
    void update(int node, int l, int r, int po, int val)
    {
        if (l == r)
        {
            seg[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (po <= m)
            update(2 * node, l, m, po, val);
        else
            update(2 * node + 1, m + 1, r, po, val);
        seg[node] = (seg[2 * node] + seg[2 * node + 1]);
    }
};

SegTree seg;
int dp[MAXN];

signed main()
{
    int n;
    scanf("%d", &n);
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    for (int k = 1; k <= n; k++)
    {
        dp[k] = INF;
        vector<int> nv, po(k + 1);
        for (int i = 1; i <= n; i++)
            if (v[i] <= k)
                nv.push_back(v[i]);
            
        for (int i = 0; i < k; i++)
            po[nv[i]] = (i + 1);
        
        seg.init(1, 1, k);
        int calc = 0;
        for (int i = k; i >= 1; i--)
        {
            calc += (k - po[i]);
            calc -= seg.query(1, 1, k, 1, po[i]);
            seg.update(1, 1, k, po[i], 1);
            dp[k] = min(dp[k], dp[i - 1] + calc);
        }
    }
    printf("%d\n", dp[n]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~

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