// Tanawin Thongbai
#include <bits/extc++.h>
using namespace std;
class Fenw_Elem {
public:
int sum, cnt, i;
Fenw_Elem() {
sum = 0;
cnt = 0;
i = 0;
}
Fenw_Elem(int sum, int cnt, int i) {
this -> sum = sum;
this -> cnt = cnt;
this -> i = i;
}
bool operator == (const Fenw_Elem &rhs) const {
return i == rhs.i && sum == rhs.sum && cnt == rhs.cnt;
}
};
const int N = 5000;
int orig[N + 1], indices[N + 1], less_before[N + 1][N + 1], cnts[N + 1][N + 2], dp_L[N + 1][N + 1], dp[N + 1];
Fenw_Elem fenw_merge(const Fenw_Elem &a, const Fenw_Elem &b) {
if(b.i == 0) {
return Fenw_Elem(a.sum + b.sum, a.cnt + b.cnt, a.i);
}
return Fenw_Elem(a.sum + b.sum + (a.i - b.i) * a.cnt, a.cnt + b.cnt, b.i == 0? a.i: min(a.i, b.i));
}
Fenw_Elem fenw_query(Fenw_Elem *fenw, const int &n, int i) {
stack<int> stk = stack<int>();
for(; i >= 1; i -= i & -i) {
stk.push(i);
}
Fenw_Elem ans = fenw[stk.top()];
stk.pop();
while(!stk.empty()) {
ans = fenw_merge(ans, fenw[stk.top()]);
stk.pop();
}
return ans;
}
void fenw_add(Fenw_Elem *fenw, const int &n, int i, int seq_i) {
for(; i <= n; i += i & -i) {
Fenw_Elem f = fenw[i];
fenw[i] = Fenw_Elem(f.sum + seq_i - f.i, f.cnt + 1, f.i);
}
}
void fenw_add_blank(Fenw_Elem *fenw, const int &n, int i, int seq_i) {
for(; i <= n; i += i & -i) {
Fenw_Elem f = fenw[i];
fenw[i] = Fenw_Elem(f.sum, f.cnt, seq_i);
}
}
int main() {
int n_elem;
scanf("%d", &n_elem);
for(int i = 1; i <= n_elem; ++i) {
scanf("%d", &orig[i]);
indices[orig[i]] = i;
}
for(int i = 1; i <= n_elem; ++i) {
int cnt = 1;
for(int j = 1; j <= n_elem; ++j) {
if(i >= orig[j]) {
cnts[i][j] = cnt++;
}
}
int cnt_less = 0;
for(int j = 1; j <= n_elem; ++j) {
if(orig[j] < i) {
++cnt_less;
}
less_before[i][j] = cnt_less;
}
}
for(int i = 1; i <= n_elem - 1; ++i) {
dp_L[i][i] = 0;
int k = 1e9;
for(int j = i + 1; j <= n_elem; ++j) {
int mv = 0;
if(k > indices[j - 1]) {
k = indices[j - 1];
}
if(k != 1e9 && k < indices[j]) {
mv = less_before[j][indices[j]] - less_before[j][k] - less_before[i][indices[j]] + less_before[i][k] + 1;
}
dp_L[i][j] = mv + dp_L[i][j - 1];
}
}
for(int i = 1; i <= n_elem; ++i) {
Fenw_Elem *fenw = new Fenw_Elem[n_elem + 1]{};
deque<int> deq = deque<int>();
for(int j = 1; j <= n_elem; ++j) {
if(cnts[i][n_elem - j + 1] > 0) {
fenw_add_blank(fenw, n_elem, j, cnts[i][n_elem - j + 1]);
}
if(orig[j] > i) {
continue;
}
if(deq.empty() || orig[deq.back()] < orig[j]) {
deq.push_back(j);
}
}
int mn = 1e9;
for(int j = 0; j <= i - 1; ++j) {
while(!deq.empty() && orig[deq.front()] <= j) {
deq.pop_front();
}
if(j > 0) {
fenw_add(fenw, n_elem, n_elem - indices[j] + 1, cnts[i][indices[j]]);
}
int mv = 0;
if(j > 0 && !deq.empty()) {
int k = deq.front();
Fenw_Elem ans = fenw_query(fenw, n_elem, n_elem - k + 1);
mv = ans.sum == 0? 0: ans.sum - ans.cnt + 1;
}
mn = min(mn, dp[j] + dp_L[j + 1][i] + mv);
}
dp[i] = mn;
delete[] fenw;
}
printf("%d\n", dp[n_elem]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d", &n_elem);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &orig[i]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
