Submission #940256

#	Time	Username	Problem	Language	Result	Execution time	Memory
940256		Angus_Yeung	Group Photo (JOI21_ho_t3)	C++14	44 / 100	5032 ms	4252 KiB

Main

#include <bits/stdc++.h>
#define len first
#define node second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

ll n, a[5010], dp[5010], pos[5010], tmp;
vector<ll> p[5010];

ll f(ll id, ll l, ll r) {
	if (l > r) return 0;
	return upper_bound(p[id].begin(), p[id].end(), r)-lower_bound(p[id].begin(), p[id].end(), l);
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
		for (int j = 1; j < i; j++) p[i].push_back(a[j]);
		sort(p[i].begin(), p[i].end());
	}
	
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = INF;
		for (int j = 1; j <= i; j++) {
			tmp = 0;
			for (int k = j; k <= i; k++) {
				tmp += f(pos[i+j-k], i+1, n);
				tmp += f(pos[i+j-k], j, i+j-k-1);
			}
			dp[i] = min(dp[i], dp[j-1]+tmp);
//			cout << dp[j-1]+tmp << ' ';
//			cout << "\n";
		}
//		cout << "\n";
	}
	
	cout << dp[n] << "\n";
	
	return 0;
}
/*



*/

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