Submission #1275530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275530		mpawicka_77	Group Photo (JOI21_ho_t3)	C++20	100 / 100	275 ms	165368 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N=5e3+2, INF=1e9;
int W[N][N], M[N][N];
bool czy[N];
int a[N], dp[N];
int main()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0);

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

     for(int i=1;i<=n;i++)
     {
          for(int j=n;j>=1;j--)
          {
               W[a[i]][j]=W[a[i]][j+1];
               W[a[i]][j]+=czy[j];
          }
          czy[a[i]]=true;
     }
     for(int i=1;i<=n;i++)czy[i]=0;
     for(int i=n;i>=1;i--)
     {
          for(int j=a[i];j<=n;j++)
          {
               M[a[i]][j]=M[a[i]][j-1];
               M[a[i]][j]+=czy[j];
          }
          czy[a[i]]=true;
     }
     for(int i=1;i<=n;i++)
     {
          dp[i]=INF;
          int inw=0;
          for(int j=i-1;j>=0;j--)
          {
               inw+=W[j+1][i+1] + M[j+1][i];
               dp[i]=min(dp[j] + inw, dp[i]);
          }
     }
     cout<<dp[n]<<" ";
     return 0;
}

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