Submission #371243

#	Time	Username	Problem	Language	Result	Execution time	Memory
371243		nafis_shifat	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1422 ms	234860 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e3+5;
const int inf=1e9;
int h[mxn];
int pos[mxn];

ll dp1[mxn][mxn] = {};
ll dp2[mxn][mxn] = {};
struct BIT
{
	int bit[mxn];
	void init() {
		memset(bit,0,sizeof bit);
	}	

	void update(int p,int v) {
		if(p==0) return;
		for(;p > 0;p -=p&-p) bit[p] += v;
	}
    int query(int p) {
    	int r=0;
    	for(;p < mxn; p +=p&-p) r += bit[p];
        return r;
    }
} bt;
ll rev(int l,int r) {
	int p = l;

	bt.init();

	for(int i = 1; i < l; i++) bt.update(pos[i],1);
	ll tot = 0;
	for(int i = r; i >= l; i--) {
		tot += bt.query(pos[i]);
		bt.update(pos[i],1);		
	}
	return tot;
}



ll sor(int l,int r) {
	int p = l;

	bt.init();

	for(int i = 1; i < l; i++) bt.update(pos[i],1);
	ll tot = 0;
	for(int i = l; i <= r; i++) {
		tot += bt.query(pos[i]);
		bt.update(pos[i],1);		
	}

	return tot;
}
int main() {
	int n;
	cin >> n;

	
	for(int i = 1; i <= n; i++) {
		cin >> h[i];
		pos[h[i]] = i;
	}

	BIT bt1;
	bt1.init();

	for(int i = 1; i <= n; i++) {
		bt.init();
		for(int j = i; j <= n; j++) {
			ll v1 = bt1.query(pos[j]);
			ll v2 = j - i - bt.query(pos[j]);
			bt.update(pos[j],1);
			dp1[i][j] = dp1[i][j - 1] + v1 + v2;
		}
		bt1.update(pos[i],1);
	}

   
	for(int i = 1; i <= n; i++) {
		bt.init();
		for(int j = 1; j < i; j++) {
			bt.update(pos[j],1);
		}
		for(int j = i; j <= n; j++) {
			dp2[i][j] = dp2[i][j - 1] + bt.query(pos[j]);
			bt.update(pos[j],1);
		}
	}

	ll dp[n + 1];
	dp[0] = 0;

	for(int i = 1; i <= n; i++) {
		dp[i] = inf;
		for(int j = i; j >= 1; j--) {
			dp[i] = min(dp[i],dp[j - 1] + min(dp1[j][i],dp2[j][i]));
		}
	}

	cout<<dp[n]<<endl;


}

Compilation message (stderr)

Main.cpp: In function 'long long int rev(int, int)':
Main.cpp:30:6: warning: unused variable 'p' [-Wunused-variable]
   30 |  int p = l;
      |      ^
Main.cpp: In function 'long long int sor(int, int)':
Main.cpp:46:6: warning: unused variable 'p' [-Wunused-variable]
   46 |  int p = l;
      |      ^

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