Submission #439636

#	Time	Username	Problem	Language	Result	Execution time	Memory
439636		JovanB	Group Photo (JOI21_ho_t3)	C++17	100 / 100	691 ms	67532 KiB

Main

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

using ll = long long;
using ld = long double;

const int MAXN = 5000;

int mns[MAXN+5][MAXN+5];
int dp[MAXN+5];
int a[MAXN+5];
int pos[MAXN+5];


struct BIT{
    int n;
    int bit[MAXN+5];
    void add(int x){
        while(x <= n){
            bit[x]++;
            x += x & -x;
        }
    }
    int get(int x){
        int res = 0;
        while(x){
            res += bit[x];
            x -= x & -x;
        }
        return res;
    }
};

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    BIT bitpre;
    bitpre.n = n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    for(int l=1; l<=n; l++){
        BIT bit;
        bit.n = n;
        for(int i=1; i<=n; i++) bit.bit[i] = 0;
        for(int r=l; r<=n; r++){
            mns[l][r] = mns[l][r-1];
            mns[l][r] += bitpre.get(n) - bitpre.get(pos[r]);
            mns[l][r] += bit.get(pos[r] - 1);
            bit.add(pos[r]);
        }
        bitpre.add(pos[l]);
    }
    for(int i=1; i<=n; i++){
        dp[i] = n*n;
        for(int j=i; j>=1; j--){
            dp[i] = min(dp[i], dp[j-1] + mns[j][i]);
        }
    }
    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