Submission #939045

#	Time	Username	Problem	Language	Result	Execution time	Memory
939045		weakweakweak	Group Photo (JOI21_ho_t3)	C++17	100 / 100	726 ms	122232 KiB

Main

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

int n, dp[5100], a[5100], cost[5100][5100] = {0};
short woo[5100][5100] = {0}; //woo[i][j]代表在i前面大於j的有幾個

struct BIT {
    int n, a[5100];
    void init (int x) {
        n = x;
        memset(a, 0, sizeof(a));
    }
    void update (int i, int x) {for (;i <= n; i += i & -i) a[i] += x; }
    int query (int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) res += a[i];
        return res;
    }
} bit;


int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    memset(dp, 63, sizeof(dp));
    dp[0] = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    //順序數對
    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        bit.init(n);
        for (int j = 1; j <= n; j++) {
            if (a[j] < l) continue;
            cost[l][a[j]] = bit.query(a[j]);
            bit.update(a[j], 1);
        }
        for (int r = l; r <= n; r++) cost[l][r + 1] += cost[l][r];
    }
    //在我前面比r大的跟我換
    bit.init(n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 2; j++) woo[a[i]][j] = i - 1 - bit.query(j);
        bit.update(a[i], 1);
    }
    for (int r = 1; r <= n; r++) {
        int haha = 0;
        for (int l = r; l >= 1; l--) {
            haha += woo[l][r];
            cost[l][r] += haha;
        }
    }

    //dp
    for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + cost[j + 1][i]);
    cout << dp[n] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:9: warning: unused variable 'cnt' [-Wunused-variable]
   30 |     int cnt = 0;
      |         ^~~

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