Submission #493845

#	Time	Username	Problem	Language	Result	Execution time	Memory
493845		PixelCat	Group Photo (JOI21_ho_t3)	C++14	100 / 100	364 ms	532 KiB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (1000000000000000ll);
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;
 
#define LO(i) (i&(-i))
struct BIT{
	int n;
	int a[5010];
	void init(int _n){
		n=_n;
		memset(a,0,sizeof(a));
	}
	void add(int i,int x){
		while(i<=n){
			a[i]+=x;
			i+=LO(i);
		}
	}
	int ask(int i){
		int ans=0;
		while(i){
			ans+=a[i];
			i-=LO(i);
		}
		return ans;
	}
}bit;
 
int a[5010];
int pos[5010];
int no[5010];
int cost[5010][5010];
int dp[5010];
 
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// nachoneko sama & miku sama bless me >/////<
	int n; cin>>n;
	For(i,1,n){
		cin>>a[i];
		pos[a[i]]=i;
		dp[i]=9e18;
	}
	For(l,1,n){
		bit.init(n);
		int now=0;
		// int mi=l;
 
		int cnt=0;
		For(i,1,n){
			if(a[i]>=l){
				cnt++;
				no[a[i]]=cnt;
			}
		}
 
		For(r,l,n){
			now+=bit.ask(pos[r]);
			bit.add(pos[r],1);
			now+=no[r]-(r-l+1);
			dp[r]=min(dp[r],dp[l-1]+now);
			// cost[l][r]=now;
			// cout<<l<<" "<<r<<" "<<now<<"\n";
		}
	}
	// For(i,1,n){
	// 	dp[i]=cost[1][i];
	// 	For(j,1,i-1) dp[i]=min(dp[i],dp[j]+cost[j+1][i]);
	// }
	cout<<dp[n]<<"\n";
	return 0;
}

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