Submission #1056778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056778		SalihSahin	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1869 ms	327692 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define double long double
using namespace std;

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

struct SEGT{
    vector<int> tree;

    void init(int n){
        tree.assign(4*n, 0);
    }

    void update(int ind, int l, int r, int pos, int val){
        if(l == r) tree[ind] = val;
        else{
            int m = (l + r)/2;
            if(pos <= m) update(ind*2, l, m, pos, val);
            else update(ind*2+1, m+1, r, pos, val);

            tree[ind] = tree[ind*2] + tree[ind*2+1];
        }
    }

    int query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;

            return query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr);
        }
    }

    int sum(int l, int r){
        return query(1LL, 1LL, tree.size()/4, l, r);
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // dp[we put first i elements without changing order of other ones] = minimum cost to get this array
    int n;
    cin>>n;
    vector<int> a(n), dp(n+1, mod);
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    vector<int> arr[n+1];
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= a[i]; j++){
            arr[j].pb(a[i]);
        }
    }
    vector<vector<int> > cost(n+1, vector<int>(n+1, mod));
    dp[0] = 0;

    /*
    for(int i = 1; i <= n; i++){
        for(int pre = i-1; pre >= 0; pre--){
            int cst = 0, ind = 0;
            vector<int> sim = arr[pre + 1];
            for(int j = i; j >= pre + 1; j--){
                int possim = 0;
                for(int pos = 0; pos < sim.size(); pos++){
                    if(sim[pos] == j){
                        possim = pos;
                        break;
                    }
                }
                cst += possim - ind;
                for(int pos = possim; pos >= ind + 1; pos--) sim[pos] = sim[pos - 1];
                sim[ind] = j;
                ind++;
            }
            cost[pre][i] = cst;
        }
    }
    */
    vector<int> presm(n+1), ind(n+1);

    for(int arri = 1; arri <= n; arri++){
        for(int j = 0; j <= n; j++) presm[j] = 0;

        int m = arr[arri].size();
        SEGT seg;
        seg.init(n+1);
        for(int i = m-1; i >= 0; i--){
            int val = arr[arri][i];
            presm[val] = seg.sum(1, val - 1);
            ind[val] = i;
            seg.update(1, 1, n+1, val, 1);
        }

        int cnt = 0;
        for(int j = arri; j <= n; j++){
            cnt += (ind[j] - presm[j]);
            cost[arri - 1][j] = cnt;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int pre = i-1; pre >= 0; pre--){
            dp[i] = min(dp[i], dp[pre] + cost[pre][i]);
        }
    }

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

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