// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 5e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
int p[N], rv[N];
int sm[N][N];
int dp[N];
int C2(int x){ return x * (x - 1) / 2; }
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
rv[p[i]] = i;
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(p[i] > p[j])
sm[i][j] ++;
}
}
for(int i = 1; i <= n; i++)
for(int j = i - 1; j >= 1; j--)
sm[j][i] += sm[j + 1][i] + sm[j][i - 1] - sm[j + 1][i - 1];
memset(dp, 31, sizeof dp);
dp[0] = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j <= n; j++)
dp[j] = min(dp[j], dp[i] - sm[i + 1][j] + C2(j - i) - sm[i + 1][j]);
}
cout << dp[n] + sm[1][n] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
