Submission #960274

#	Time	Username	Problem	Language	Result	Execution time	Memory
960274		mickytanawin	Group Photo (JOI21_ho_t3)	C++17	100 / 100	272 ms	97896 KiB

Main

// Tanawin Thongbai

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


const int N = 5000;

int orig[N + 1], indices[N + 1], obstruct[N + 1], obstructed[N + 1], obstructed_at[N + 1], dp_L[N + 1][N + 1], dp[N + 1];


int main() {
    int n_elem;
    scanf("%d", &n_elem);
    for(int i = 1; i <= n_elem; ++i) {
        scanf("%d", &orig[i]);
        indices[orig[i]] = i;
    }
    for(int j = 1; j <= n_elem; ++j) {
        dp_L[j][j] = 0;
        int mv = 0;
        for(int i = j - 1; i >= 1; --i) {
            if(indices[i] < indices[j]) {
                ++mv;
            }
            dp_L[i][j] = dp_L[i][j - 1] + mv;
        }
    }
    for(int i = 1; i <= n_elem; ++i) {
        for(int j = indices[i] + 1; j <= n_elem; ++j) {
            if(orig[j] < i) {
                ++obstruct[i];
            }
        }
        for(int j = indices[i] - 1; j >= 1; --j) {
            if(orig[j] > i) {
                ++obstructed[i];
            }
        }
    }
    for(int i = 1; i <= n_elem; ++i) {
        int mn = 1e9;
        int mv = 0;
        int k = n_elem + 1;
        int cnt = 0;
        for(int j = 1; j <= n_elem; ++j) {
            obstructed_at[j] = cnt;
            if(orig[j] > i) {
                ++cnt;
            }
        }
        for(int j = i; j >= 1; --j) {
            if(indices[j] > k) {
                mv += obstruct[j] - obstructed[j] + obstructed_at[indices[j]];
            } else {
                mv += obstruct[j];
            }
            if(indices[j] < k) {
                k = indices[j];
            }
            mn = min(mn, dp[j - 1] + dp_L[j][i] + mv);
        }
        dp[i] = mn;
    }
    printf("%d\n", dp[n_elem]);

    return 0;
}

Compilation message (stderr)

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

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