Submission #1161345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161345		tw20000807	Group Photo (JOI21_ho_t3)	C++20	64 / 100	5092 ms	584 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;

struct BIT{
    int n;
    vector< int > tree;
    BIT(int N){
        n = N;
        tree.resize(n + 1);
    }
    void modify(int id, int val){
        for(; id <= n; id += id & -id) tree[id] += val;
    }
    int query(int id){
        int ret = 0;
        for(; id; id -= id & -id) ret += tree[id];
        return ret;
    }
};
void sol(){
    int n; cin >> n;
    vector< int > v(n + 2), dp(n + 2, llmx), p(n + 2);
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        p[v[i]] = i;
    }
    dp[0] = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < i; ++j){
            int cost = 0;
            BIT bit(n + 1);
            for(int t = n; t > i; --t) bit.modify(p[t], 1);

            for(int k = j + 1; k <= i; ++k){
                cost += bit.query(p[k]);
                bit.modify(p[k], 1);
            }
            // cerr << i << " " << j << " " << cost << "!!\n";
            dp[i] = min(dp[i], dp[j] + cost);
        }
    }
    cout << dp[n] << "\n";
}
/*
5
3 5 2 4 1

// 3

5
3 2 1 5 4
// 0


9
6 1 3 4 9 5 7 8 2
// 9

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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