oj.uz

Submission #873762

# Submission time Handle Problem Language Result Execution time Memory
873762 2023-11-15T16:54:59 Z tvladm2009 Group Photo (JOI21_ho_t3) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1E9;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

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

    int n;
    std::cin >> n;
    std::vector<int> a(n + 1), pos(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        pos[a[i] - 1] = i - 1;
    }

    std::vector<int> dp(n + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = inf;
        Fenwick<int> fen(n);
        int cur = 0;
        for (int j = i - 1; j >= 0; j--) {
            cur += fen.rangeSum(pos[j], n) - fen.sum(pos[j]);
            fen.add(pos[j], 1);
            dp[i] = std::min(dp[i], dp[j] + cur);
        }
    }
    int answer = dp[n];
    Fenwick<int> fen(n);
    for (int i = 1; i <= n; i++) {
        answer += fen.rangeSum(pos[i], n);
        fen.add(pos[i], 1);
    }
    std::cout << answer << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -