Submission #508668

#	Time	Username	Problem	Language	Result	Execution time	Memory
508668		cig32	Group Photo (JOI21_ho_t3)	C++17	100 / 100	541 ms	294232 KiB

Main

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5030;
const int MOD = 1e9 + 7;
//#define int long long    

int rnd(int x, int y) { // random number generator
  int u= uniform_int_distribution<int>(x, y)(rng); return u;
}

void solve(int tc) {
  int n;
  cin >> n;
  int h[n+1];
  for(int i=1; i<=n; i++) cin >> h[i];
  int pos[n+1];
  for(int i=1; i<=n; i++) pos[h[i]] = i;
  int inv[n+1][n+1];
  for(int i=0; i<=n; i++) {
      for(int j=0; j<=n; j++) {
          inv[i][j] = 0;
      }
  }
  for(int i=1; i<=n; i++) {
      for(int j=i+1; j<=n; j++) {
          if(h[i] > h[j]) {
              inv[1][h[i]]++;
              inv[h[j] + 1][h[i]]--;
          }
      }
  }
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
          inv[i][j] += inv[i][j-1] + inv[i-1][j] - inv[i-1][j-1];
      }
  }
  int ext_pos[n+1][n+1];
  for(int i=0; i<=n; i++) {
      for(int j=0; j<=n; j++) {
          ext_pos[i][j] = 0;
      }
  }
  int right[n+1][n+1];
  for(int i=0; i<=n; i++) {
      for(int j=0; j<=n; j++) {
          right[i][j] = 0;
      }
  }
  for(int i=n-1; i>=1; i--) {
      for(int j=0; j<=n; j++) {
          right[h[i]][j] = right[h[i+1]][j] + (h[i+1] <= j);
      }
  }
  for(int i=1; i<=n; i++) {
      for(int j=0; j<=n; j++) {
          ext_pos[i][j] = pos[i] + right[i][j];
      }
  }
  for(int i=2; i<=n; i++) {
      for(int j=0; j<=n; j++) {
          ext_pos[i][j] += ext_pos[i-1][j];
      }
  }
  int dp[n+1];
  for(int i=0; i<=n; i++) dp[i] = 1e9;
  dp[0] = 0;
  for(int i=1; i<=n; i++) {
      for(int j=0; j<i; j++) {
          int ref = inv[j+1][i];
          int sz = i-j;
          int mx = sz * (sz-1) / 2;
          int ono = ext_pos[i][j] - ext_pos[j][j];
          int rem = (j+1 + i) * (i - (j+1) + 1) / 2;
          dp[i] = min(dp[i], dp[j] + mx - ref + ono - rem);
      }
  }
  cout << dp[n] << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

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