제출 #1154006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154006		ReLice	Group Photo (JOI21_ho_t3)	C++20	100 / 100	2116 ms	117868 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e12;
const ll mod = 1e9 + 7;
const ll N = 5e3 + 8;

struct seg{
    ll t[N * 4];

    void upd(ll v, ll tl, ll tr, ll pos, ll val){
        if(tl > pos || tr < pos) return;
        if(tl == tr){
            t[v] = val;
            return;
        }
        ll tm = (tl + tr) / 2;

        upd(v * 2, tl, tm, pos, val);
        upd(v * 2 + 1, tm + 1, tr, pos, val);

        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    void upd(ll pos, ll val){
        upd(1, 1, N - 1, pos, val);
    }

    ll get(ll v, ll tl, ll tr, ll l, ll r){
        if(tl > r || tr < l) return 0;
        if(l <= tl && tr <= r) return t[v];
        ll tm = (tl + tr) / 2;

        return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
    }
    ll get(ll l, ll r){
        return get(1, 1, N - 1, l, r);
    }
}t;

ll dp[N];
ll id[N][N];

void solve() {
    ll i, j;

    ll n;
    cin>>n;

    ll a[n + 1];
    ll pos[n + 1];

    for(i=1;i<=n;i++) {
        cin>>a[i];
        pos[a[i]] = i;
    }
    for(i=0;i<n;i++){
        ll c = 0;
        for(j=1;j<=n;j++){
            if(a[j] > i) {
                id[i][a[j]] = c++;
            }
        }
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    for(i=0;i<n;i++){
        ll sum = 0;
        for(j=i + 1;j<=n;j++){
            sum += id[i][j];
            t.upd(pos[j], 1);
            sum -= t.get(pos[j] + 1, n);

            dp[j] = min(dp[j], dp[i] + sum);
        }

        for(j=1;j<N * 4;j++) t.t[j] = 0;
    }

    cout<<dp[n]<<endl;
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*
12 1
))())((()(()
My answer
3
Correct answer
((()(()))())
1 8
4
*/

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