Submission #536100

#	Time	Username	Problem	Language	Result	Execution time	Memory
536100		victor_gao	Group Photo (JOI21_ho_t3)	C++17	100 / 100	1148 ms	732 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 5015 
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int dp[N],h[N],pos[N],d[N],n;
struct BIT{
	int arr[N];
	int lowbit(int x){
		return x&-x;
	}
	void reset(){
		for (int i=0;i<=n;i++) arr[i]=0;
	}
	void change(int p,int v){
		for (;p<=n;p+=lowbit(p)){
			arr[p]+=v;
		}
	}
	int query(int x){
		int ans=0;
		for (;x>0;x-=lowbit(x)){
			ans+=arr[x];
		}
		return ans;
	}
}bit,bit2;
signed main(){
	fast
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>h[i];
		pos[h[i]]=i;
		dp[i]=1e9;
	}
	for (int i=1;i<=n;i++) bit.change(i,1);
	for (int i=0;i<=n;i++){
		if (i){
			bit.change(1,1);
			bit.change(pos[i],-1);
		}
	//	for (int j=1;j<=n;j++) cout<<bit.query(j)<<' ';
	//	cout<<'\n';
		int tans=0;
		vector<pii>bk;
		for (int j=i+1;j<=n;j++){
			int np=bit.query(pos[j]);
			tans+=abs(np-(i+1));
			tans-=2*(j-i-1-bit2.query(pos[j]));
			bit.change(1,1);
			bit.change(pos[j],-1);
			bit2.change(pos[j],1);
			bk.push_back({1,-1});
			bk.push_back({pos[j],1});
			dp[j]=min(dp[j],dp[i]+tans);
			//cout<<i+1<<" ~ "<<j<<" -> "<<dp[i]<<" "<<tans<<'\n';
		}
		bit2.reset();
		for (auto j:bk) bit.change(j.x,j.y);
	//	cout<<dp[i]<<"\n";
	}
	cout<<dp[n]<<'\n';
}

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