Submission #1125672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125672		Kel_Mahmut	Group Photo (JOI21_ho_t3)	C++20	100 / 100	998 ms	196576 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct fenwick{
	int n;
	vector<int> fen;
	fenwick(int n) : n(n), fen(n){}

	void upd(int pos, int val){
		for(int i = pos; i < n; i |= (i + 1))
			fen[i] += val;
	};

	int query(int pos){
		int ret = 0;
		for(int i = pos; i >= 0; i = (i & (i + 1)) - 1)
			ret += fen[i];
		return ret;
	}

	int query(int ql, int qr){
		return query(qr) - query(ql - 1);
	}
};

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i], a[i]--;
	vector<int> pos(n);
	for(int i = 0; i < n; i++) pos[a[i]] = i;
	vector<vector<int>> inv(n, vector<int>(n));
	for(int r = n - 1; r >= 0; r--){
		fenwick st(n);
		int cur = 0;
		for(int l = r; l >= 0; l--){
			cur += st.query(pos[l], n - 1);
			inv[l][r] = cur;
			st.upd(pos[l], 1);
		}
	}

	vector<vector<int>> cros(n + 1, vector<int>(n + 1));
	for(int l = 0; l <= n; l++){
		fenwick st(n);
		for(int i = 1; i <= l; i++){
			st.upd(pos[i - 1], 1);
		}
		int cur = 0;
		for(int r = l + 1; r <= n; r++){
			cur += st.query(pos[r - 1], n - 1);
			cros[l][r] = cur;
		}
	}

	vector<int> dp(n + 1);
	for(int k = 1; k <= n; k++){
		dp[k] = INT_MAX;
		for(int j = 0; j < k; j++){
			dp[k] = min(dp[k], dp[j] + inv[j][k - 1] + cros[j][k]);
		}
	}
	cout << dp[n] << endl;
}

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