This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define se second
#define fs first
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 5e3 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;
int n, Q;
int a[N];
int pos[N];
int cnt[N][N], cost[N][N];
int dp[N];
void solution () {
cin >> n;
rep (i, 1, n) {
cin >> a[i];
pos[a[i]] = i;
}
rep (i, 1, n) {
rep (j, 1, n) {
cnt[i][j] = cnt[i - 1][j] + (a[i] >= j);
}
}
rep (i, 1, n)
rep (j, i, n) {
cost[i][j] = cost[i][j - 1] + cnt[pos[j]][i] - cnt[pos[j]][j];
}
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
rep (i, 1, n) {
int curcost = 0;
reb (j, i, 1) {
curcost += cnt[pos[j]][i + 1];
dp[i]= min(dp[i], dp[j - 1] + curcost + cost[j][i]);
}
}
cout << dp[n] <<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |