Submission #538498

#	Time	Username	Problem	Language	Result	Execution time	Memory
538498		Haruto810198	Group Photo (JOI21_ho_t3)	C++17	100 / 100	999 ms	509808 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 5010;

int n;
int arr[MAX][MAX]; // arr[i] = arr. after sorting [1, i]
int pos[MAX][MAX];
int cost[MAX][MAX]; // cost[i][j] = cost to sort [i, j]
int dp[MAX];
int res;

inline int sum(int l, int r){
	return (l + r) * (r - l + 1) / 2;
}

#define lsb(x) ((x)&(-(x)))

int BIT[MAX];

void modify(int pos, int val){
	while(pos < MAX){
		BIT[pos] += val;
		pos += lsb(pos);
	}
}

int query(int pos){
	int ret = 0;
	while(pos > 0){
		ret += BIT[pos];
		pos -= lsb(pos);
	}
	return ret;
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[0][i];
	}

	FOR(i, 1, n, 1){
		int ptr;
		FOR(j, 1, n, 1){
			arr[i][j] = arr[i-1][j];
			if(arr[i][j] == i) ptr = j;
		}

		while(ptr > i){
			swap(arr[i][ptr-1], arr[i][ptr]);
			ptr--;
		}
	}
	
	FOR(i, 0, n, 1){
		FOR(j, 1, n, 1){
			pos[i][ arr[i][j] ] = j;
		}
	}
	
	FOR(l, 1, n, 1){
		int dpos = 0;
		int inv = 0;
		FOR(r, l, n, 1){
			// cost[l, r]

			dpos += pos[l-1][r] - r;
			inv += query(pos[l-1][r] - 1);
			modify(pos[l-1][r], 1);

			cost[l][r] = dpos + inv;
		}
		
		FOR(r, l, n, 1){
			modify(pos[l-1][r], -1);
		}
	}

	FOR(r, 1, n, 1){
		dp[r] = LNF;
		FOR(l, 1, r, 1){
			dp[r] = min(dp[r], dp[l-1] + cost[l][r]);
		}
	}

	cout<<dp[n]<<'\n';
	/*
	FOR(l, 1, n, 1){
		cerr<<"cost["<<l<<"] : ";
		FOR(r, 1, n, 1){
			cerr<<cost[l][r]<<" ";
		}
		cerr<<endl;
	}
	cerr<<endl;
	*/
	return 0;

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:7: warning: 'ptr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |   int ptr;
      |       ^~~

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