Submission #380814

#	Time	Username	Problem	Language	Result	Execution time	Memory
380814		anonymous	Group Photo (JOI21_ho_t3)	C++14	100 / 100	649 ms	98700 KiB

Main

#include <iostream>
#define MAXN 5005
using namespace std;

int N, H[MAXN], pos[MAXN];
int psum[MAXN][MAXN],dp[MAXN];

int main() {
    scanf("%d",&N);
    for (int i=1; i<=N; i++) {
        scanf("%d",&H[i]);
        pos[H[i]] = i;
    }
    //do prefix sum
    for (int i=1; i <= N; i++) {
        for (int h=1; h <= N; h++) {
            psum[i][h] = psum[i-1][h] + psum[i][h-1] + (H[i] == h) - psum[i-1][h-1];
        }
    }

    //dp
    for (int i=N-1; i>=1; i--) {
        dp[i] = 1<<30; //subsequence i...N
        int cost = 0;
        for (int j=i; j <= N; j++) {
            cost += 2*(psum[pos[j]][j-1]-psum[pos[j]][i-1])-(j-i)+(psum[pos[j]][N]-psum[pos[j]][j]);
            dp[i] = min(dp[i], dp[j+1] + cost);
        }
    }

    printf("%d",dp[1]);
}

Compilation message (stderr)

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

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