Submission #915789

#	Time	Username	Problem	Language	Result	Execution time	Memory
915789		ace5	Group Photo (JOI21_ho_t3)	C++17	100 / 100	160 ms	117644 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5001;

short lsf[maxn][maxn];
int otr[maxn][maxn];
int dp[maxn];
int h[maxn];
int ih[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0;i < n;++i)
    {
        cin >> h[i];
        h[i]--;
        ih[h[i]] = i;
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = n-1;j >= 0;--j)
        {
            lsf[i][j] = (j == n-1 ? ih[i] > ih[j] : (ih[i] > ih[j]) + lsf[i][j+1]);
        }
    }
    for(int l = 0;l < n;++l)
    {
        for(int r = l;r < n;++r)
        {
            otr[l][r] = (l == r ? lsf[l][l] : lsf[r][l]*2 - lsf[r][r] - r + l + otr[l][r-1]);
        }
    }
    dp[n] = 0;
    for(int i = n-1;i >= 0;--i)
    {
        dp[i] = 1e9;
        for(int j = i+1;j <= n;++j)
        {
            dp[i] = min(dp[i],dp[j] + otr[i][j-1]);
        }
    }
    cout << dp[0];
    return 0;
}

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