Submission #1034982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034982		juicy	Group Photo (JOI21_ho_t3)	C++17	100 / 100	316 ms	134480 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e3 + 5;

int n;
int h[N], pos[N], f[N][N], g[N][N], dp[N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i];
    pos[h[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = n; j >= i; --j) {
      f[i][j] = f[i][j + 1] + (pos[j] < pos[i]);
    }
    for (int j = i; j > 0; --j) {
      g[j][i] = g[j + 1][i] + (pos[j] < pos[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i - 2; j >= 1; --j) {
      f[j][i] += f[j + 1][i];
    }
    for (int j = i + 2; j <= n; ++j) {
      g[i][j] += g[i][j - 1];
    }
  } 
  memset(dp, 0x3f, sizeof(dp));
  dp[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      dp[i] = min(dp[i], dp[j] + f[j + 1][i + 1] + g[j + 1][i]);
    }
  }
  cout << dp[n];
  return 0;
}

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