Submission #1230664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230664		biank	Group Photo (JOI21_ho_t3)	C++20	100 / 100	460 ms	196640 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vi h(n);
    forn(i, n) cin >> h[i], --h[i];
    vi pos(n);
    forn(i, n) pos[h[i]] = i;
    vll dp(n + 1, INF);
    dp[0] = 0LL;
    vector<vi> pref(n, vi(n + 1));
    forn(i, n) forn(j, n) {
        pref[i][j + 1] = pref[i][j] + (pos[j] < pos[i]);
    }
    vector<vi> pref2(n + 1, vi(n));
    forn(i, n) forn(j, n) {
        pref2[i + 1][j] = pref2[i][j] + (pos[j] < pos[i]);
    }
    forsn(i, 1, n + 1) {
        ll cost = 0LL;
        dforn(j, i) {
            cost += pref2[i][j] - pref2[j][j];
            cost += pref[j][n] - pref[j][j];
            cost -= pref[j][i] - pref[j][j];
            dp[i] = min(dp[i], dp[j] + cost);
        }
    }
    cout << dp[n] << '\n';
    
    return 0;
}

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