Submission #704036

#	Time	Username	Problem	Language	Result	Execution time	Memory
704036		onlk97	Group Photo (JOI21_ho_t3)	C++14	100 / 100	764 ms	98412 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct bit{
    int b[5010];
    void cl(){
        for (int i=0; i<5010; i++) b[i]=0;
    }
    void update(int pos,int val){
        for (int i=pos; i<5010; i+=i&(-i)) b[i]+=val;
    }
    int query(int pos){
        int ans=0;
        for (int i=pos; i; i-=i&(-i)) ans+=b[i];
        return ans;
    }
};
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    int a[n+1];
    for (int i=1; i<=n; i++) cin>>a[i];
    int pos[n+1];
    for (int i=1; i<=n; i++) pos[a[i]]=i;
    int cost[n+1][n+1];
    bit out,in;
    for (int i=1; i<=n; i++){
        out.cl(); in.cl();
        for (int j=i+1; j<=n; j++) out.update(pos[j],1);
        int cnt=0;
        for (int j=i; j>0; j--){
            cnt+=out.query(pos[j]);
            cnt+=in.query(n+1-pos[j]);
            in.update(n+1-pos[j],1);
            cost[j][i]=cnt;
        }
    }
    int dp[n+1];
    dp[0]=0;
    for (int i=1; i<=n; i++) dp[i]=1e9;
    for (int i=1; i<=n; i++){
        for (int j=0; j<i; j++) dp[i]=min(dp[i],dp[j]+cost[j+1][i]);
    }
    cout<<dp[n]<<'\n';
}

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