Submission #807716

#	Time	Username	Problem	Language	Result	Execution time	Memory
807716		dong_liu	Group Photo (JOI21_ho_t3)	C++17	100 / 100	309 ms	98324 KiB

Main

#include <iostream>
using namespace std;

const int N = 5e3;

int main() {
  int n;
  scanf("%d", &n);
  static int o[N + 1];
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    o[a] = i;
  }
  static int s[N + 1][N + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      s[i][j] =
          s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (i < j && o[i] > o[j]);
  auto inv = [&](int i1, int i2, int j1, int j2) {
    return s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1];
  };
  auto ninv = [&](int i, int j) {
    return (j - i + 1) * (j - i) / 2 - inv(i, j, i, j);
  };
  static int f[N + 1];
  for (int i = 1; i <= n; i++) {
    f[i] = ninv(1, i);
    for (int j = 1; j < i; j++)
      f[i] = min(f[i], f[j] + inv(1, j, j + 1, i) + ninv(j + 1, i));
  }
  printf("%d\n", f[n]);
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d", &a);
      |     ~~~~~^~~~~~~~~~

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