Submission #503511

#	Time	Username	Problem	Language	Result	Execution time	Memory
503511		InternetPerson10	Group Photo (JOI21_ho_t3)	C++17	100 / 100	768 ms	313296 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll BIG = 1234567891234567890;

ll ans[5001];
ll dp[5001][5001];
ll permute_people[5001][5001]; // Permute people [i, j] once they are already on the left
ll push_people[5001][5001]; // Push people [i, j] to the left

struct FTree {
    vector<int> nums;
    int size = 1;
    void init(int n) {
        vector<int>().swap(nums);
        size = 1;
        while(size <= n) size *= 2;
        nums.resize(size+1);
    }
    void add(int n, int k) {
        while(n <= size) {
            nums[n] += k;
            n += (n & (-n));
        }
    }
    int sum(int n) {
        int ans = 0;
        while(n) {
            ans += nums[n];
            n -= (n & (-n));
        }
        return ans;
    }
};

ll swap_photo(vector<int> nums) {
    int n = nums.size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    }
    vector<int> ind(n);
    for(int i = 0; i < n; i++) ind[nums[i]] = i;
    FTree ft, ft2;
    for(int i = 0; i < n; i++) {
        ft.init(n+1);
        ft2.init(n+1);
        for(int j = i; j < n; j++) ft2.add(ind[j]+1, 1);
        for(int j = i; j < n; j++) {
            if(i == j) push_people[i][j] = ft2.sum(ind[j]+1) - 1;
            else push_people[i][j] = push_people[i][j-1] + ft2.sum(ind[j]+1) - 1 - (j - i) + ft.sum(ind[j]+1);
            ft.add(ind[j]+1, 1);
        }
    }
    for(int i = n-1; i >= 0; i--) {
        ans[i] = BIG;
        for(int j = i; j < n; j++) {
            dp[i][j] = push_people[i][j] + ans[j+1];
            ans[i] = min(ans[i], dp[i][j]);
        }
    }
    return ans[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    for(int i = 0; i < n; i++) nums[i]--;
    cout << swap_photo(nums);
}

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