Submission #470056

#	Time	Username	Problem	Language	Result	Execution time	Memory
470056		vincent97198	Group Photo (JOI21_ho_t3)	C++14	100 / 100	918 ms	584 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

int calc[5005][5005];
int BIT[5005][2];

inline int lowbit(int x)
{
    return x&(-x);
}

inline void add(int pos,int val,int st)
{
    for(;pos<5005;pos+=lowbit(pos))
        BIT[pos][st]+=val;
}

inline int sum(int pos,int st)
{
    int ret=0;
    for(;pos>0;pos-=lowbit(pos))
        ret+=BIT[pos][st];
    return ret;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);   cout.tie(nullptr);

    int n;  cin >> n;
    vector<int> h(n+1),pos(n+1);

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


    vector<int> dp(n+1,1e18);
    dp[0]=0;
    for(int i=1;i<=n;++i){
        int calc=0;
        for(int k=1;k<=i;++k) add(pos[k],1,0);
        for(int j=i-1;j>=0;--j){
            calc+=j+1-sum(pos[j+1],0);
            calc-=sum(pos[j+1],1);
            calc+=(i-j-1)-sum(pos[j+1],1);
            add(pos[j+1],-1,0);
            add(pos[j+1],1,1);
            dp[i]=min(dp[i],dp[j]+calc);
        }
        for(int k=0;k<5005;++k) BIT[k][1]=0;
    }
    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