Submission #937820

#	Time	Username	Problem	Language	Result	Execution time	Memory
937820		Andrey	Group Photo (JOI21_ho_t3)	C++14	100 / 100	945 ms	900 KiB

Main

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

vector<int> dp(5001,INT_MAX);
vector<int> idk(5001);
int n;

void upd(int a, int x) {
    while(a <= n) {
        idk[a]+=x;
        a+=(a&(-a));
    }
}

int calc(int a) {
    int c = 0,sb = 0;
    for(int i = 12; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            sb+=idk[c];
        }
    }
    return sb;
}

void dude(vector<int> haha) {
    int n = haha.size()-1;
    vector<int> p(n+1);
    for(int i = 1; i <= n; i++) {
        p[haha[i]] = i;
    }
    int br = 0;
    for(int i = 0; i <= n; i++) {
        idk[i] = 0;
    }
    for(int i = n; i >= 1; i--) {
        br+=n-p[i];
        br-=calc(p[i]);
        upd(p[i],1);
        dp[n] = min(dp[n],dp[i-1]+br);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    dp[0] = 0;
    vector<int> haha(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    for(int i = 1; i <= n; i++) {
        vector<int> bruh(1);
        for(int j = 1; j <= n; j++) {
            if(haha[j] <= i) {
                bruh.push_back(haha[j]);
            }
        }
        dude(bruh);
    }
    cout << dp[n];
    return 0;
}

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