Submission #1144557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144557		fryingduc	Group Photo (JOI21_ho_t3)	C++20	100 / 100	230 ms	196396 KiB

Main

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5005;
int n, a[maxn], pos[maxn];
int c[maxn][maxn], d[maxn][maxn], f[maxn];

void solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      c[i][j] = c[i][j - 1] + (i > j and pos[i] < pos[j]);
      d[i][j] = d[i][j - 1] + (i > j and pos[i] > pos[j]);
    }
    for(int j = 1; j <= n; ++j) {
      c[i][j] += c[i - 1][j], d[i][j] += d[i - 1][j];
    }
  }
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= i; ++j) {
      int cost = c[i][j - 1] - c[j - 1][j - 1] + d[i][i] - d[i][j - 1];
      f[i] = min(f[i], cost + f[j - 1]);
    }
  }
  cout << f[n];
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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