Submission #371041

#	Time	Username	Problem	Language	Result	Execution time	Memory
371041		valerikk	Group Photo (JOI21_ho_t3)	C++17	100 / 100	513 ms	512 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

struct Fenwick {
  int n;
  vector <int> t;
  
  void add(int pos, int delta) {
    for (int i = pos + 1; i <= n; i += i & -i) t[i] += delta;
  }

  int get(int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= i & -i) sum += t[i];
    return sum;
  }

  int get(int l, int r) {
    return get(r) - get(l);
  }

  Fenwick(int nn) : n(nn) {
    t = vector <int>(n + 1, 0);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector <int> h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  vector <int> pos(n);
  for (int i = 0; i < n; i++) {
    h[i]--;
    pos[h[i]] = i;
  }
  const int inf = 1e9;
  vector <int> dp(n + 1);
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    dp[i + 1] = inf;
    Fenwick f(n);
    int cur = 0;
    for (int j = i; j >= 0; j--) {
      cur += f.get(pos[j], n) - f.get(pos[j]);
      f.add(pos[j], 1);
      dp[i + 1] = min(dp[i + 1], dp[j] + cur);
    }
  }
  int ans = dp[n];
  Fenwick f(n);
  for (int i = 0; i < n; i++) {
    ans += f.get(pos[i], n);
    f.add(pos[i], 1);
  }
  cout << ans << endl;
  return 0;
}

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