oj.uz

Submission #758902

# Submission time Handle Problem Language Result Execution time Memory
758902 2023-06-15T13:40:25 Z 1075508020060209tc Group Photo (JOI21_ho_t3) C++14
0 / 100
 1 ms 300 KB 
#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]){cal++;}
                }
            }
        }
        if(j==0){dp[i]=cal;}
        dp[i]=min(dp[i],cal);
    }
}
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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -