Submission #758905

#	Time	Username	Problem	Language	Result	Execution time	Memory
758905		1075508020060209tc	Group Photo (JOI21_ho_t3)	C++14	44 / 100	5061 ms	308 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long

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<=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++;}
                }
            }
        }
        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: 0 / 20
• Subtask 5: 0 / 36