Submission #634787

#	Time	Username	Problem	Language	Result	Execution time	Memory
634787		mdn2002	Group Photo (JOI21_ho_t3)	C++14	100 / 100	901 ms	393032 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n , a [5003] , bs [5003][5003] , wr [5003] , dp [5003][5003];
int f ( int x , int y )
{
    if ( x == n + 1 ) return 0;
    if ( dp [x][y] != -1 ) return dp [x][y];
    int ans = 1e9 , pos = x , posx = wr [y] + bs [y][ x - 1 ] , howmany = ( bs [y][ y - 1 ] - bs [y][ x - 1 ] );
    if ( x != y ) ans = min ( ans , f ( y , y ) );
    if ( y != n + 1 ) ans = min ( ans , f ( x , y + 1 ) + posx - pos - howmany );
    return dp [x][y] = ans;
}
int main ()
{
    memset ( dp , -1 , sizeof dp );
    cin >> n;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        cin >> a [i];
        wr [ a [i] ] = i;
    }
    for ( int i = 1 ; i <= n ; i ++ )
    {
        for ( int j = i ; j <= n ; j ++ ) bs [ a [i] ][ a [j] ] ++;
        for ( int j = 1 ; j <= n ; j ++ ) bs [ a [i] ][j] += bs [ a [i] ][ j - 1 ];
    }
    cout << f ( 1 , 1 );
}

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