Submission #1229409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229409		almaharbas4	Group Photo (JOI21_ho_t3)	C++20	100 / 100	315 ms	516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int maxn=5005;
vector<int> bit(maxn),dp(maxn),pref(maxn);
void update(int i,int a,int n)
{
    for(;i<=n;i+=i&-i) bit[i]+=a;
}
int sum(int i)
{
    int s=0;
    for(;i;i-=i&-i) s+=bit[i];
    return s;
}
int main()
{
    int n;
    cin>>n;
    vector<int> v(maxn);
    vector<int> pos(maxn);
    for(int i=1;i<=n;i++) 
    {
        cin>>v[i];
        pos[v[i]]=i;
        dp[i]=1e9;
    }
    for(int i=1;i<=n;i++)
    {
        int s=0;
        for(int j=1;j<=n;j++) pref[j]=pref[j-1]+(v[j]>=i);
        for(int j=i;j<=n;j++)
        {
            s+=pref[pos[j]]-j+i-1+sum(pos[j]);
            dp[j]=min(dp[j],dp[i-1]+s);
            update(pos[j],1,n);
        }
        for(int j=0;j<=n;j++) bit[j]=0;
    }
    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