oj.uz

Submission #940247

# Submission time Handle Problem Language Result Execution time Memory
940247 2024-03-07T07:00:49 Z Angus_Yeung Group Photo (JOI21_ho_t3) C++14
0 / 100
 1 ms 344 KB 
#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, k-1);
			}
			dp[i] = min(dp[i], dp[j-1]+tmp);
//			cout << dp[j-1]+tmp << ' ';
		}
//		cout << "\n";
	}
	
	cout << dp[n]-1 << "\n";
	
	return 0;
}
/*



*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -