Submission #625124

#	Time	Username	Problem	Language	Result	Execution time	Memory
625124		Abrar_Al_Samit	Group Photo (JOI21_ho_t3)	C++17	100 / 100	707 ms	67728 KiB

Main

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

const int MX = 5004;

int n;
int a[MX];
int cost[MX][MX];
int bit[MX];

void add(int id, int delta) {
  for(int i=id; i<=n; i=i|(i+1)) {
    bit[i] += delta;
  }
}
int sum(int r) {
  int ret = 0;
  for(int i=r; i>=0; i=(i&(i+1))-1) {
    ret += bit[i];
  }
  return ret;
}
int sum(int l, int r) {
  return sum(r) - sum(l-1);
}


int dp[MX];
int solve(int i) {
  if(i>n) return 0;
  int &ret = dp[i];
  if(ret!=-1) return ret;
  ret = INT_MAX;

  for(int j=i; j<=n; ++j) {
    ret = min(ret, solve(j+1)+cost[i][j]);
  }
  return ret;
}
int alt[MX];
void PlayGround() {
  cin>>n;
  for(int i=1; i<=n; ++i) {
    cin>>a[i];
    alt[a[i]] = i;
  }

  int inv[n+1] = {};
  for(int i=1; i<=n; ++i) {
    for(int j=alt[i]-1; j>0; --j) if(a[j]>i) {
      ++inv[i];
    }
  }

  for(int j=1; j<=n; ++j) {
    memset(bit, 0, sizeof bit);
    for(int i=j; i>0; --i) {
      cost[i][j] = inv[i] - sum(1, alt[i]) + sum(alt[i], n);
      if(i!=j) cost[i][j] += cost[i+1][j];
      add(alt[i], 1);
    }
  }

  memset(dp, -1, sizeof dp);
  cout<<solve(1)<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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