Submission #476061

#	Time	Username	Problem	Language	Result	Execution time	Memory
476061		Jarif_Rahman	Group Photo (JOI21_ho_t3)	C++17	100 / 100	676 ms	392328 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<vector<ll>> dp(n, vector<ll>(n, inf));
    vector<vector<ll>> inv(n, vector<ll>(n, 0));

    vector<int> v(n);
    for(int &x: v) cin >> x, x--;
    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[v[i]] = i;

    for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) if(pos[i] < pos[j]) inv[i][j]++;
    for(int i = 0; i < n; i++) for(int j = 0; j+i < n; j++){
        int l = j, r = j+i;
        if(l == r) continue;
        inv[l][r]+=inv[l][r-1]+inv[l+1][r]-inv[l+1][r-1];
    }

    vector<ll> mn(n, inf);

    for(int i = n-1; i >= 0; i--){
        vector<ll> sum(n, 0);
        for(int j = 0; j < n; j++) if(v[j] > i) sum[j]++;
        for(int j = 1; j < n; j++) sum[j]+=sum[j-1];
        ll c = 0;
        for(int j = i; j >= 0; j--){
            c+=sum[pos[j]];
            dp[i][j] = inv[j][i]+c;
            if(i != n-1) dp[i][j]+=mn[i];
            if(j != 0) mn[j-1] = min(mn[j-1], dp[i][j]);
        }
    }

    ll ans = inf;
    for(int i = 0; i < n; i++) ans = min(ans, dp[i][0]);
    cout << ans << "\n";
}

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