Submission #1000153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000153		DobromirAngelov	Group Photo (JOI21_ho_t3)	C++14	100 / 100	312 ms	98648 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=5e3+5;

int n;
int a[MAXN];
int cnt[MAXN][MAXN];
int dp[MAXN];

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++) cnt[a[j]][a[i]]++;
}
for(int i=1;i<=n;i++)
{
    for(int j=i-1;j>=1;j--) cnt[i][j]+=cnt[i][j+1];
}
for(int j=1;j<=n;j++)
{
    for(int i=j+1;i<=n;i++) cnt[i][j]+=cnt[i-1][j];
}
for(int i=1;i<=n;i++)
{
    for(int j=n;j>i;j--) cnt[i][j]+=cnt[i][j+1];
}
for(int j=n;j>=1;j--)
{
    for(int i=1;i<j;i++) cnt[i][j]+=cnt[i-1][j];
}

dp[n+1]=0;
for(int i=n;i>=1;i--)
{
    dp[i]=1e9;
    for(int j=i;j<=n;j++)
    {
        dp[i]=min(dp[i], (cnt[j][i]-cnt[i][i])+(cnt[j][j+1]-cnt[i-1][j+1])+dp[j+1]);
    }
}

cout<<dp[1]<<endl;

return 0;
}

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