Submission #938548

#	Time	Username	Problem	Language	Result	Execution time	Memory
938548		the_coding_pooh	Group Photo (JOI21_ho_t3)	C++14	100 / 100	283 ms	840 KiB

Main

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

#define int _int
using _int = long long;

const int SIZE = 5e3 + 5, INF = 1e9 + 7;

int dp[SIZE];

struct BITree{
    int BIT[SIZE];

    void init(){
        for (int i = 0; i < SIZE;i++){
            BIT[i] = 0;
        }
        return;
    }

    void modify(int pos, int val){
        for (; pos < SIZE;pos += (pos & -pos)){
            BIT[pos] += val;
        }
        return;
    }

    int query(int pos){
        int ret = 0;
        for (; pos; pos -= (pos & -pos)){
            ret += BIT[pos];
        }
        return ret;
    }

}lss_amnt, grt_amnt;

int N;

int pos[SIZE];

signed main(){
    cin >> N;
    int in_i;
    for (int i = 1; i <= N;i++){
        cin >> in_i;
        pos[in_i] = i;
    }

    int shift;

    //dp[i] = with i ~ i inserted, the minimum numbers of switch needed

    for (int i = 1; i <= N;i++){
        shift = 0;
        dp[i] = INF;
        grt_amnt.init();
        lss_amnt.modify(pos[i], 1);
        //from j to i is the last decreasing
        for (int j = i; j >= 1;j--){
            shift += i - lss_amnt.query(pos[j]) - grt_amnt.query(pos[j]);
            dp[i] = min(dp[i], dp[j - 1] + shift);
            grt_amnt.modify(pos[j], 1);
        }
    }

    cout << dp[N] << '\n';
}

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