제출 #1161356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161356		tw20000807	Group Photo (JOI21_ho_t3)	C++20	100 / 100	468 ms	636 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;
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
};
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){
        BIT bit(n + 1), bit2(n + 1);

        for(int t = n; t > i; --t) bit.modify(p[t], 1);
        int cost = 0;
        for(int j = i - 1; j >= 0; --j){
            // cerr << i << " " << j << " " << cost << "!!\n";
            cost += bit.query(p[j + 1]) + bit2.query(p[j + 1], n);

            dp[i] = min(dp[i], dp[j] + cost);
            bit2.modify(p[j + 1], 1);
        }
    }
    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: 36 / 36