#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e3+5;
const int inf=1e9;
int h[mxn];
int pos[mxn];
ll dp1[mxn][mxn] = {};
ll dp2[mxn][mxn] = {};
struct BIT
{
int bit[mxn];
void init() {
memset(bit,0,sizeof bit);
}
void update(int p,int v) {
if(p==0) return;
for(;p > 0;p -=p&-p) bit[p] += v;
}
int query(int p) {
int r=0;
for(;p < mxn; p +=p&-p) r += bit[p];
return r;
}
} bt;
ll rev(int l,int r) {
int p = l;
bt.init();
for(int i = 1; i < l; i++) bt.update(pos[i],1);
ll tot = 0;
for(int i = r; i >= l; i--) {
tot += bt.query(pos[i]);
bt.update(pos[i],1);
}
return tot;
}
ll sor(int l,int r) {
int p = l;
bt.init();
for(int i = 1; i < l; i++) bt.update(pos[i],1);
ll tot = 0;
for(int i = l; i <= r; i++) {
tot += bt.query(pos[i]);
bt.update(pos[i],1);
}
return tot;
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> h[i];
pos[h[i]] = i;
}
BIT bt1;
bt1.init();
for(int i = 1; i <= n; i++) {
bt.init();
for(int j = i; j <= n; j++) {
ll v1 = bt1.query(pos[j]);
ll v2 = j - i - bt.query(pos[j]);
bt.update(pos[j],1);
dp1[i][j] = dp1[i][j - 1] + v1 + v2;
}
bt1.update(pos[i],1);
}
for(int i = 1; i <= n; i++) {
bt.init();
for(int j = 1; j < i; j++) {
bt.update(pos[j],1);
}
for(int j = i; j <= n; j++) {
dp2[i][j] = dp2[i][j - 1] + bt.query(pos[j]);
bt.update(pos[j],1);
}
}
ll dp[n + 1];
dp[0] = 0;
for(int i = 1; i <= n; i++) {
dp[i] = inf;
for(int j = i; j >= 1; j--) {
dp[i] = min(dp[i],dp[j - 1] + min(dp1[j][i],dp2[j][i]));
}
}
cout<<dp[n]<<endl;
}
Compilation message
Main.cpp: In function 'long long int rev(int, int)':
Main.cpp:30:6: warning: unused variable 'p' [-Wunused-variable]
30 | int p = l;
| ^
Main.cpp: In function 'long long int sor(int, int)':
Main.cpp:46:6: warning: unused variable 'p' [-Wunused-variable]
46 | int p = l;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
4 ms |
2284 KB |
Output is correct |
22 |
Correct |
4 ms |
2284 KB |
Output is correct |
23 |
Correct |
4 ms |
2432 KB |
Output is correct |
24 |
Correct |
4 ms |
2284 KB |
Output is correct |
25 |
Correct |
4 ms |
2284 KB |
Output is correct |
26 |
Correct |
4 ms |
2284 KB |
Output is correct |
27 |
Correct |
4 ms |
2284 KB |
Output is correct |
28 |
Correct |
4 ms |
2284 KB |
Output is correct |
29 |
Correct |
4 ms |
2284 KB |
Output is correct |
30 |
Correct |
4 ms |
2284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
4 ms |
2284 KB |
Output is correct |
22 |
Correct |
4 ms |
2284 KB |
Output is correct |
23 |
Correct |
4 ms |
2432 KB |
Output is correct |
24 |
Correct |
4 ms |
2284 KB |
Output is correct |
25 |
Correct |
4 ms |
2284 KB |
Output is correct |
26 |
Correct |
4 ms |
2284 KB |
Output is correct |
27 |
Correct |
4 ms |
2284 KB |
Output is correct |
28 |
Correct |
4 ms |
2284 KB |
Output is correct |
29 |
Correct |
4 ms |
2284 KB |
Output is correct |
30 |
Correct |
4 ms |
2284 KB |
Output is correct |
31 |
Correct |
37 ms |
11884 KB |
Output is correct |
32 |
Correct |
34 ms |
11884 KB |
Output is correct |
33 |
Correct |
35 ms |
11884 KB |
Output is correct |
34 |
Correct |
35 ms |
11884 KB |
Output is correct |
35 |
Correct |
34 ms |
11884 KB |
Output is correct |
36 |
Correct |
34 ms |
11884 KB |
Output is correct |
37 |
Correct |
35 ms |
12012 KB |
Output is correct |
38 |
Correct |
35 ms |
11884 KB |
Output is correct |
39 |
Correct |
34 ms |
11884 KB |
Output is correct |
40 |
Correct |
34 ms |
11884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
4 ms |
2284 KB |
Output is correct |
22 |
Correct |
4 ms |
2284 KB |
Output is correct |
23 |
Correct |
4 ms |
2432 KB |
Output is correct |
24 |
Correct |
4 ms |
2284 KB |
Output is correct |
25 |
Correct |
4 ms |
2284 KB |
Output is correct |
26 |
Correct |
4 ms |
2284 KB |
Output is correct |
27 |
Correct |
4 ms |
2284 KB |
Output is correct |
28 |
Correct |
4 ms |
2284 KB |
Output is correct |
29 |
Correct |
4 ms |
2284 KB |
Output is correct |
30 |
Correct |
4 ms |
2284 KB |
Output is correct |
31 |
Correct |
37 ms |
11884 KB |
Output is correct |
32 |
Correct |
34 ms |
11884 KB |
Output is correct |
33 |
Correct |
35 ms |
11884 KB |
Output is correct |
34 |
Correct |
35 ms |
11884 KB |
Output is correct |
35 |
Correct |
34 ms |
11884 KB |
Output is correct |
36 |
Correct |
34 ms |
11884 KB |
Output is correct |
37 |
Correct |
35 ms |
12012 KB |
Output is correct |
38 |
Correct |
35 ms |
11884 KB |
Output is correct |
39 |
Correct |
34 ms |
11884 KB |
Output is correct |
40 |
Correct |
34 ms |
11884 KB |
Output is correct |
41 |
Correct |
1400 ms |
234476 KB |
Output is correct |
42 |
Correct |
1402 ms |
234476 KB |
Output is correct |
43 |
Correct |
1422 ms |
234428 KB |
Output is correct |
44 |
Correct |
1406 ms |
234520 KB |
Output is correct |
45 |
Correct |
1403 ms |
234348 KB |
Output is correct |
46 |
Correct |
1402 ms |
234604 KB |
Output is correct |
47 |
Correct |
1416 ms |
234732 KB |
Output is correct |
48 |
Correct |
1399 ms |
234860 KB |
Output is correct |
49 |
Correct |
1420 ms |
234476 KB |
Output is correct |
50 |
Correct |
1410 ms |
234732 KB |
Output is correct |
51 |
Correct |
1415 ms |
234732 KB |
Output is correct |
52 |
Correct |
1408 ms |
234604 KB |
Output is correct |
53 |
Correct |
1407 ms |
234720 KB |
Output is correct |
54 |
Correct |
1403 ms |
234476 KB |
Output is correct |
55 |
Correct |
1404 ms |
234508 KB |
Output is correct |