Submission #1221189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221189		AlgorithmWarrior	Group Photo (JOI21_ho_t3)	C++20	100 / 100	286 ms	516 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n;
int const NMAX=5005;
int v[NMAX];
int pos[NMAX];

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

int ub(int x){
    return x&(-x);
}

struct fenwick_tree{
    int v[NMAX];
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
    void _clear(){
        int i;
        for(i=1;i<=n;++i)
            v[i]=0;
    }
    int sum_range(int l,int r){
        return sum(r)-sum(l-1);
    }
}aib[2];

int dp[NMAX];
int const INF=1e9;

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int solve(){
    dp[0]=0;
    int i,j;
    for(i=1;i<=n;++i)
        dp[i]=INF;
    for(i=0;i<n;++i){
        aib[1]._clear();
        int total=0;
        for(j=i+1;j<=n;++j){
            total+=pos[j]-1-aib[0].sum(pos[j]-1)-aib[1].sum_range(pos[j]+1,n);
            minself(dp[j],dp[i]+total);
            aib[1].add(pos[j],1);
        }
        aib[0].add(pos[i+1],1);
    }
    return dp[n];
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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