Submission #387459

#	Time	Username	Problem	Language	Result	Execution time	Memory
387459		uacoder123	Group Photo (JOI21_ho_t3)	C++14	100 / 100	818 ms	232556 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n;
int h[5001],dp[5001][5001],p[5001],ans[5001];
int dp1[5001][5001],dp2[5001][5001];
int main()
{

      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
  cin>>n;
  for(int i=0;i<n;++i)
  {
    cin>>h[i];
    h[i]--;
    p[h[i]]=i;
  }
  for(int i=0;i<n;++i)
  {
    int v=0,v1=0;
    for(int j=i-1;j>=0;--j)
    {
      if(p[j]<p[i])
      {
        v=1;
        v1=0;
      }
      else
      {
        v1=1;
        v=0;
      }
      dp2[i][j]=dp2[i][j+1]+v1;
      dp1[i][j]=dp1[i][j+1]+v;
    }
    for(int j=i+1;j<n;++j)
    {
      if(p[j]<p[i])
        v=1;
      else
        v=0;
      dp1[i][j]=dp1[i][j-1]+v;
    }
  }
  for(int i=0;i<n;++i)
  {
    dp[i][i]=0;
    for(int j=i+1;j<n;++j)
      dp[i][j]=dp[i][j-1]+dp1[j][i];
  }
  for(int i=0;i<n;++i)
  {
    int v1=0,v2;
  int ans1=n*n;
    for(int j=i;j>=0;--j)
    {
      v1-=dp1[j][i];
      v1+=dp2[j][0];
      if(j-1==-1)
        v2=0;
      else
        v2=ans[j-1];
      ans1=min(ans1,v1+dp[j][i]+v2);
    }
    ans[i]=ans1;
  }
  cout<<ans[n-1]<<endl;
  return 0;
}

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