Submission #1221968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221968		TadijaSebez	Group Photo (JOI21_ho_t3)	C++20	100 / 100	218 ms	99764 KiB

Main

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

const int N=5050;
int cnt[N][N],h[N],pos[N];
int dp[N];

const int inf=1e9+7;

int main(){
    int n;
    scanf("%i",&n);
    for(int i=1;i<=n;i++){
        scanf("%i",&h[i]);
        pos[h[i]]=i;
        for(int j=1;j<=n;j++){
            cnt[i][j]=cnt[i-1][j]+(h[i]<=j);
        }
    }
    for(int i=1;i<=n;i++){
        int add=0;
        dp[i]=inf;
        for(int j=i;j>=1;j--){
            add+=(j-1)-cnt[pos[j]-1][j];
            int tmp=cnt[pos[j]-1][i]-cnt[pos[j]-1][j];
            add-=tmp;
            add+=(i-j)-tmp;
            dp[i]=min(dp[i],dp[j-1]+add);
        }
    }
    printf("%i\n",dp[n]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%i",&h[i]);
      |         ~~~~~^~~~~~~~~~~~

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