Submission #759228

#	Time	Username	Problem	Language	Result	Execution time	Memory
759228		1075508020060209tc	Group Photo (JOI21_ho_t3)	C++14	64 / 100	5056 ms	468 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 dp[5010];


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

dp[0]=0;
for(int i=1;i<=n;i++){

    for(int j=0;j<=i-1;j++){
        int cal=dp[j];
        for(int a=1;a<=5000;a++){
            bit[a]=0;
        }

        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);
            }
        }
        if(j==0){dp[i]=cal;}
        dp[i]=min(dp[i],cal);
    }
   // 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: 0 / 36