Submission #733250

#	Time	Username	Problem	Language	Result	Execution time	Memory
733250		tch1cherin	Group Photo (JOI21_ho_t3)	C++17	100 / 100	464 ms	468 KiB

Main

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

struct fenwick {
  int N;
  vector<int> F;

  fenwick(int n) : N(n), F(n + 1) {}

  void add(int i, int v) {
    for (i++; i <= N; i += i & -i) {
      F[i] += v;
    }
  }

  int query(int r) {
    int ans = 0;
    for (; r > 0; r -= r & -r) {
      ans += F[r];
    }
    return ans;
  }
};

void solve() {
  int N;
  cin >> N;
  vector<int> H(N);
  for (int &v : H) {
    cin >> v;
    v--;
  }
  vector<int> pos(N);
  for (int i = 0; i < N; i++) {
    pos[H[i]] = i;
  }
  vector<int> p(N);
  fenwick f(N);
  for (int i = 0; i < N; i++) {
    p[i] = i - f.query(pos[i]); 
    f.add(pos[i], 1);
  }
  vector<long long> dp(N + 1);
  for (int i = 0; i < N; i++) {
    fenwick right(N);
    long long I = 0, X = 0;
    dp[i + 1] = LLONG_MAX; 
    for (int l = i; l >= 0; l--) {
      X += p[l] - right.query(pos[l]);  
      I += right.query(pos[l]);
      dp[i + 1] = min(dp[i + 1], dp[l] + min(I, 1ll * (i - l) * (i - l + 1) / 2 - I) + X);
      right.add(pos[l], 1);  
    }
  }
  cout << dp[N] << "\n";
}

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

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