Submission #587717

#	Time	Username	Problem	Language	Result	Execution time	Memory
587717		Peti	Group Photo (JOI21_ho_t3)	C++14	100 / 100	323 ms	134224 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5000;

int utan[maxn][maxn], ert[maxn][maxn];

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

    int n;
    cin>>n;
    vector<int> v(n), inv(n);
    for(int i = 0; i < n; i++){
        cin>>v[i];
        --v[i];
        inv[v[i]] = i;
    }

    for(int i = 0; i < n; i++)
        for(int j = i-1; j >= 0; j--)
            utan[i][j] = utan[i][j+1] + (inv[i] < inv[j] ? 1 : 0);

    vector<int> db(n);
    iota(db.begin(), db.end(), 0);
    for(int i = 0; i < n; i++){
        ert[i][i] = db[inv[i]];
        for(int j = i+1; j < n; j++)
            ert[i][j] = ert[i][j-1] + db[inv[j]] - utan[j][i];
        for(int j = inv[i]+1; j < n; j++)
            db[j]--;
    }

    /*cout<<"ert:\n";
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++)
            cout<<ert[i][j]<<' ';
        cout<<'\n';
    }*/

    vector<int> dp(n+1, (int)1e9);
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i; j > 0; j--)
            dp[i] = min(dp[i], dp[j-1] + ert[j-1][i-1]);
    cout<<dp[n]<<'\n';

    return 0;
}

/*
5
3 5 2 4 1
*/

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