Submission #927841

#	Time	Username	Problem	Language	Result	Execution time	Memory
927841		Unforgettablepl	Group Photo (JOI21_ho_t3)	C++17	100 / 100	363 ms	852 KiB

Main

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

#define int long long

const int INF = 1e15;

struct fenwick{
    int n;
    vector<int> tree;
    fenwick(int n):n(n),tree(n+1){}
    int get(int k){
        int ans = 0;
        while(k){
            ans+=tree[k];
            k-=k&-k;
        }
        return ans;
    }
    void add(int k){
        while(k<=n){
            tree[k]++;
            k+=k&-k;
        }
    }
};

int DP[5001];
int idx[5001];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        idx[a]=i;
    }
    fenwick elements(n);
    for(int i=1;i<=n;i++){
        elements.add(idx[i]);
        int curr = 0;
        DP[i] = INF;
        fenwick bigger(n);
        for(int j=i;j;j--){
            curr+=elements.get(n);
            curr-=elements.get(idx[j]);
            curr-=bigger.get(idx[j]);
            bigger.add(idx[j]);
            DP[i] = min(DP[i],DP[j-1]+curr);
        }
    }
    cout << DP[n] << '\n';
}

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