Submission #700912

#	Time	Username	Problem	Language	Result	Execution time	Memory
700912		bebra	Group Photo (JOI21_ho_t3)	C++17	12 / 100	1189 ms	82516 KiB

Main

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

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 20;
const int MAX_MASK = 1 << MAX_N;
int dp[MAX_MASK][MAX_N];
const int INF = 1e9;


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

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

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            if (!(mask & (1 << i))) continue;
            int cnt = __builtin_popcount(mask);
            if (cnt == 1) {
                dp[mask][i] = pos[i];
                break;
            }
            int cnt_less = 0;
            for (int j = 0; j < n; ++j) {
                if ((mask & (1 << j)) && (pos[j] > pos[i])) {
                    ++cnt_less;
                }
            }
            int swaps_n = abs((cnt - 1) - (pos[i] + cnt_less));
            dp[mask][i] = INF;
            for (int j = 0; j < i + 2; ++j) {
                if (i == j) continue;
                if (!(mask & (1 << j))) continue;
                dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + swaps_n);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    cout << ans << '\n';
    
    return 0;
}

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