Submission #601514

#	Time	Username	Problem	Language	Result	Execution time	Memory
601514		pakhomovee	Group Photo (JOI21_ho_t3)	C++17	100 / 100	530 ms	293952 KiB

Main

//  by pakhomovee
#include <iomanip>
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <cmath>
#include <unordered_map>
#include <cassert>
#include <queue>
#include <unordered_set>
#include <chrono>

using namespace std;
using namespace chrono;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define all(a) a.begin(), a.end()
#define double long double
#define ll long long
#define dbg(x) std::cerr << #x << ": " << x << '\n';
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define FEL(a, x) for (auto& a : x)
#define REV reverse
#define asrt assert
#define ll long long
#define unique1(x) x.resize(unique(all(x)) - x.begin())

const double eps = 1e-7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> pos(n);
    for (int& i : a) {
        cin >> i;
        --i;
    }
    for (int i = 0; i < n; ++i) {
        pos[a[i]] = i;
    }
    vector<int> dp(n + 1, 2e9);
    int cost[n][n];
    int inv[n][n];
    int rinv[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cost[i][j] = inv[i][j] = rinv[i][j] = 0;
        }
    }
    vector<int> withBigger(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] > a[i]) {
                ++withBigger[a[i]];
            }
        }
    }
    for (int j = 0; j < n; ++j) {
        int curr = 0;
        for (int i = j - 1; i >= 0; --i) {
            if (pos[j] < pos[i]) {
                ++curr;
            }
            inv[j][i] = curr;
        }
    }
    for (int j = 0; j < n; ++j) {
        int curr = 0;
        for (int i = j - 1; i >= 0; --i) {
            if (pos[j] > pos[i]) {
                ++curr;
            }
            rinv[j][i] = curr;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int need = cost[i][j - 1];
            int ps = pos[j];
            need += rinv[j][i];
            cost[i][j] = need;
        }
    }
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i; j < n; ++j) {
            sum += withBigger[j];
            sum -= inv[j][i];
            if (j != n - 1) {
                cost[i][j] += sum;
            }
            /*for (int k = n - 1; k >= 0; --k) {
                if (a[k] >= i && a[k] <= j) {
                    ++cnt;
                }
                if (a[k] > j) {
                    cost[i][j] += cnt;
                }
            }*/
        }
    }
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j >= 1; --j) {
            dp[i] = min(dp[i], dp[j - 1] + cost[j - 1][i - 1]);
        }
    }
    cout << dp.back();
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:85:17: warning: unused variable 'ps' [-Wunused-variable]
   85 |             int ps = pos[j];
      |                 ^~

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