Submission #508666

#	Time	Username	Problem	Language	Result	Execution time	Memory
508666		cig32	Group Photo (JOI21_ho_t3)	C++17	64 / 100	5062 ms	98000 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]) {
              for(int k=1; k<=h[j]; k++) inv[k][h[i]]++;
          }
      }
  }
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
          inv[i][j] += inv[i][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;
          //cout << i << " " << j << " " << mx << " " << ref << " ";
          //cout << ono << " " << rem << "\n";
          dp[i] = min(dp[i], dp[j] + mx - ref + ono - rem);
      }
  }
  cout << dp[n] << "\n";
  /*
  cout << "dp array:\n";
  for(int i=1; i<=n; i++) {
      cout << dp[i] << " ";
  }
  cout << "\n";
  cout << "inv array:\n";
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
          cout << inv[i][j] << " ";
      }
      cout << "\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: 0 / 36