#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 5005;
int dp[N], a[N], pos[N];
int inv[N][N], is[N][N];
int pref[N][N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n;i++) cin>>a[i], a[i]--, pos[a[i]] = i;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
is[i][j] = (pos[i] < pos[j]);
if(i && j) pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
else if(i) pref[i][j] = pref[i-1][j];
else if(j) pref[i][j] = pref[i][j-1];
pref[i][j] += is[i][j];
}
}
auto get = [&](int i, int x, int j, int y){
if(i < x) swap(i, x);
if(j < y) swap(j, y);
return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
};
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
inv[i][j] = inv[i][j-1] + get(i, j - 1, j, j);
}
}
//~ for(int i=0;i<n;i++){
//~ for(int j=i;j<n;j++) cout<<inv[i][j]<<" ";
//~ cout<<"\n";
//~ }
for(int i=n-1;~i;i--){
dp[i] = 1e9;
for(int j=1;i+j<=n;j++){
dp[i] = min(dp[i], dp[i+j] + inv[i][i+j-1] + (i ? get(i, i+j-1, 0, i - 1) : 0));
}
}
//~ for(int i=0;i<n;i++) cout<<dp[i]<<" ";
//~ cout<<"\n";
cout<<dp[0]<<"\n";
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:30:39: warning: array subscript -2 is below array bounds of 'long long int [5005]' [-Warray-bounds]
30 | return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
| ~~~~~~~~~~~^
Main.cpp:30:96: warning: array subscript -2 is below array bounds of 'long long int [5005]' [-Warray-bounds]
30 | return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
| ~~~~~~~~~~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
452 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
572 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
576 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
452 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
572 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
576 KB |
Output is correct |
| 21 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 22 |
Correct |
2 ms |
3516 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3520 KB |
Output is correct |
| 24 |
Correct |
2 ms |
3524 KB |
Output is correct |
| 25 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 27 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 28 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 29 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 30 |
Correct |
2 ms |
3532 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
452 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
572 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
576 KB |
Output is correct |
| 21 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 22 |
Correct |
2 ms |
3516 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3520 KB |
Output is correct |
| 24 |
Correct |
2 ms |
3524 KB |
Output is correct |
| 25 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 27 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 28 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 29 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 30 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 31 |
Correct |
16 ms |
22460 KB |
Output is correct |
| 32 |
Correct |
15 ms |
22552 KB |
Output is correct |
| 33 |
Correct |
15 ms |
22464 KB |
Output is correct |
| 34 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 35 |
Correct |
16 ms |
22604 KB |
Output is correct |
| 36 |
Correct |
15 ms |
22512 KB |
Output is correct |
| 37 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 38 |
Correct |
15 ms |
22576 KB |
Output is correct |
| 39 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 40 |
Correct |
15 ms |
22592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
452 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
572 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
576 KB |
Output is correct |
| 21 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 22 |
Correct |
2 ms |
3516 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3520 KB |
Output is correct |
| 24 |
Correct |
2 ms |
3524 KB |
Output is correct |
| 25 |
Correct |
2 ms |
3512 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 27 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 28 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 29 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 30 |
Correct |
2 ms |
3532 KB |
Output is correct |
| 31 |
Correct |
16 ms |
22460 KB |
Output is correct |
| 32 |
Correct |
15 ms |
22552 KB |
Output is correct |
| 33 |
Correct |
15 ms |
22464 KB |
Output is correct |
| 34 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 35 |
Correct |
16 ms |
22604 KB |
Output is correct |
| 36 |
Correct |
15 ms |
22512 KB |
Output is correct |
| 37 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 38 |
Correct |
15 ms |
22576 KB |
Output is correct |
| 39 |
Correct |
15 ms |
22604 KB |
Output is correct |
| 40 |
Correct |
15 ms |
22592 KB |
Output is correct |
| 41 |
Correct |
662 ms |
508856 KB |
Output is correct |
| 42 |
Correct |
661 ms |
508972 KB |
Output is correct |
| 43 |
Correct |
666 ms |
509080 KB |
Output is correct |
| 44 |
Correct |
636 ms |
509008 KB |
Output is correct |
| 45 |
Correct |
643 ms |
509100 KB |
Output is correct |
| 46 |
Correct |
664 ms |
509248 KB |
Output is correct |
| 47 |
Correct |
708 ms |
509340 KB |
Output is correct |
| 48 |
Correct |
741 ms |
509156 KB |
Output is correct |
| 49 |
Correct |
769 ms |
509152 KB |
Output is correct |
| 50 |
Correct |
800 ms |
509124 KB |
Output is correct |
| 51 |
Correct |
781 ms |
509208 KB |
Output is correct |
| 52 |
Correct |
771 ms |
509160 KB |
Output is correct |
| 53 |
Correct |
752 ms |
509212 KB |
Output is correct |
| 54 |
Correct |
817 ms |
509096 KB |
Output is correct |
| 55 |
Correct |
729 ms |
509140 KB |
Output is correct |
