Submission #535731

#	Time	Username	Problem	Language	Result	Execution time	Memory
535731		sam571128	Group Photo (JOI21_ho_t3)	C++17	100 / 100	709 ms	117600 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 5e3+5;
int bit[N][2], inv[N][N];

void update(int idx, int pos, int val){
    while(pos < N){
        bit[pos][idx] += val;
        pos += pos&-pos;
    }
}

int query(int idx, int pos){
    int res = 0;
    while(pos){
        res += bit[pos][idx];
        pos -= pos&-pos;
    }
    return res;
}

signed main(){
    fastio
    int n;
    cin >> n;
    int pos[n+1] = {};

    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        pos[x] = i;
    }

    int arr[n+1];
    iota(arr,arr+n+1,0);
    for(int i = 1;i <= n;i++){
        arr[i] = pos[arr[i]];
    }

    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= n;j++){
            bit[j][0] = 0;
        }
        for(int j = i;j <= n;j++){
            inv[i][j] = inv[i][j-1] + query(0,arr[j]) + query(1,N-1) - query(1,arr[j]);
            update(0,arr[j],1); 
        }
        update(1,arr[i],1);
    }

    int dp[n+1] = {};
    fill(dp+1,dp+n+1,1e18);

    for(int i = 1;i <= n;i++){
        for(int j = 0;j < i;j++){
            dp[i] = min(dp[i],dp[j] + inv[j+1][i]);
            //inv => inversions after reverse
        }
    }

    cout << dp[n] << "\n";
}

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