Submission #998378

#	Time	Username	Problem	Language	Result	Execution time	Memory
998378		MarwenElarbi	Group Photo (JOI21_ho_t3)	C++17	100 / 100	332 ms	196420 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=1e5+5;
int main() {
    int n;
    cin>>n;
    int tab[n+1];
    int pos[n+1];
    for (int i = 1; i <= n; ++i)
    {
        cin>>tab[i];
        pos[tab[i]]=i;
    }
    int pre[n+1][n+1];
    int cost[n+1][n+1];
    memset(pre,0,sizeof pre);
    memset(cost,0,sizeof cost);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            pre[i][j]=pre[i][j-1]+(pos[j]>pos[i]);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
        {
            cost[i][j]+=pre[j][i-1];
            if(j>i){
                cost[i][j]+=cost[i][j-1];
                cost[i][j]+=(j-i);
                cost[i][j]-=(pre[j][j-1]-pre[j][i-1]);
            }
            //cout <<i<<" "<<j<<" "<<cost[i][j]<<endl;
        }
    }
    ll dp[n+1];
    for (int i = 0; i <= n; ++i) dp[i]=1e18;
    dp[0]=0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            dp[i]=min(dp[i],dp[j-1]+cost[j][i]);
        }
    }
    cout <<dp[n]<<endl;
}

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