Submission #536071

#	Time	Username	Problem	Language	Result	Execution time	Memory
536071		victor_gao	Group Photo (JOI21_ho_t3)	C++17	64 / 100	5051 ms	716 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';
		for (int j=i+1;j<=n;j++){
			int tans=0;
			vector<pii>bk;
			for (int k=j;k>i;k--){
				int np=bit.query(pos[k]);
				tans+=abs(np-(i+j-k+1));
				bit.change(1,1);
				bit.change(pos[k],-1);
				bk.push_back({1,-1});
				bk.push_back({pos[k],1});
			}
			dp[j]=min(dp[j],dp[i]+tans);
			for (auto k:bk){
				bit.change(k.x,k.y);
			}
		}
	//	bit2.reset();
	//	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: 0 / 36