Submission #884663

#	Time	Username	Problem	Language	Result	Execution time	Memory
884663		AlphaMale06	Group Photo (JOI21_ho_t3)	C++14	100 / 100	358 ms	97572 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 5003;
int f[N];
int cst[N][N];
int dp[N];

int lsb(int i){
    return i&-i;
}

void upd(int ind, int val){
    for(int i=ind; i<N; i+=lsb(i))f[i]+=val;
}

int get(int l){
    int ret=0;
    for(int i=l; i>0; i-=lsb(i))ret+=f[i];
    return ret;
}

int get(int l, int r){
    return get(r)-get(l-1);
}

void calccost(int a[], int n){
    for(int i=1; i<=n; i++){
        int sz=n-i+1;
        int pos[n+1];
        int b[sz];
        int skip=0;
        for(int j=0; j< n; j++){
            if(a[j]<i)skip++;
            else b[j-skip]=a[j];
            pos[a[j]]=j-skip+1;
        }
        int numinv=0;
        int sumpos=0;
        for(int j=i; j<=n; j++){
            upd(pos[j], 1);
            numinv+=get(0, pos[j]-1);
            sumpos+=pos[j];
            sumpos-=j-i+1;
            cst[i][j]=numinv+sumpos;
        }
        for(int j=0; j<N; j++){
            f[j]=0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i< n; i++)cin >> a[i];
    calccost(a, n);
    for(int i=1; i<=n; i++){
        dp[i]=1e9;
        for(int j=i-1; j>=0; j--){
            dp[i]=min(dp[i], dp[j]+cst[j+1][i]);
        }
    }
    cout << dp[n] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void calccost(int*, int)':
Main.cpp:32:13: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   32 |         int b[sz];
      |             ^

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