Submission #870860

#	Time	Username	Problem	Language	Result	Execution time	Memory
870860		adhityamv	Group Photo (JOI21_ho_t3)	C++17	100 / 100	341 ms	1100 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<ii,ii>
#define fi first
#define se second
int n;
ll bit[5001];
ll get(int ind){
    ll ans=0;
    ind++;
    while(ind>0){
        ans+=bit[ind];
        ind-=(ind&(-ind));
    }
    return ans;
}
void update(int ind,int val){
    ind++;
    while(ind<=n){
        bit[ind]+=val;
        ind+=(ind&(-ind));
    }
}
void solve(){
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
        a[i]--;
    }
    int ainv[n];
    for(int i=0;i<n;i++) ainv[a[i]]=i;
    ll dp[n+1];
    dp[0]=0;
    for(ll i=1;i<=n;i++){
        int b[i];
        int ind=0;
        for(int j=0;j<n;j++){
            if(a[j]<i){
                b[ind]=a[j];
                ind++;
            }
        }
        ll binv[i];
        for(int j=0;j<i;j++) binv[b[j]]=j;
        for(int j=0;j<=i;j++) bit[j]=0;
        dp[i]=1000000000000000000;
        ll tadd=0;
        for(ll j=1;j<=i;j++){
            tadd+=get(i-1-binv[i-j]);
            update(i-1-binv[i-j],1);
            tadd+=(i-j-binv[i-j]);
            dp[i]=min(dp[i],tadd+dp[i-j]);
        }
    }
    cout << dp[n];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:33:9: warning: variable 'ainv' set but not used [-Wunused-but-set-variable]
   33 |     int ainv[n];
      |         ^~~~

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