Submission #1184791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184791		MongHwa	Group Photo (JOI21_ho_t3)	C++20	100 / 100	241 ms	134476 KiB

Main

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
using namespace std;

#define INF 0x7f7f7f7f

int h[5005], pos[5005], mn[5005];
int psum[5005][5005], dp[5005][5005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
        pos[h[i]] = i;
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
            if(h[i] > h[j])
                psum[h[i]][h[j]] = 1;
        
        for(int j = 2; j <= h[i]; j++)
            psum[h[i]][j] += psum[h[i]][j-1];
    }

    fill(mn+1, mn+n+1, INF);
    for(int it = 1; it <= n; it++)
    {
        dp[it][it] = mn[it-1];
        for(int x = it; x <= n; x++)
        {
            int xpos = pos[x] + psum[x][it-1];
            dp[it][x] += (dp[it][x-1] + (xpos-it) - (psum[x][x]-psum[x][it-1]));

            mn[x] = min(mn[x], dp[it][x]);
        }
    }

    cout << mn[n] << '\n';
}

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