Submission #759230

#	Time	Username	Problem	Language	Result	Execution time	Memory
759230		1075508020060209tc	Group Photo (JOI21_ho_t3)	C++14	100 / 100	386 ms	516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x){return x&-x;}
int bit[200005];

void upd(int pl,int val){
while(pl<=5000){
    bit[pl]+=val;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}



int n;
int ar[5010];
int rar[5010];
int dp[5010];
int ps[5010];

signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    cin>>ar[i];
    rar[ar[i]]=i;
    dp[i]=1e16;
}

dp[0]=0;
for(int i=1;i<=n;i++){
    int cal=0;
    for(int a=1;a<=5000;a++){
        bit[a]=0;
        ps[a]=ps[a-1];
        if(ar[a]>i){ps[a]++;}
    }
 //   for(int a=1;a<=i;a++){
   //     upd(rar[a],1);
    //}


    for(int j=i-1;j>=0;j--){


/*
        for(int a=1;a<=n;a++){
            if(ar[a]>j&&ar[a]<=i){
                //for(int b=1;b<a;b++){
                  //  if((ar[b]<ar[a]&&ar[b]>j)||(ar[b]>i) ){cal++;}
                //}
                cal+=qsum(ar[a]);
            }
            if(ar[a]>j&&ar[a]<=i){
                upd(ar[a],1);
            }
            if(ar[a]>i){
                upd(1,1);
            }
        }
*/
        cal+=ps[rar[j+1]];
        upd(rar[j+1],1);
        cal+=qsum(5000)-qsum(rar[j+1]);

        dp[i]=min(dp[i],cal+dp[j]);
    }
   // cout<<dp[i]<<" ";
}
cout<<dp[n]<<endl;




}
/*
6 5
1 2 1 100000
1 3 1 1
2 6 1 1000
2 4 1 1
2 5 1 1
*/

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