#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int const maxn = 1010;
ii dp[maxn];
ii dfs(vector<int> const& p, vector<int>& vis, int i) {
if (vis[i] == 1) return dp[i];
vis[i] = 1;
ii ans = {i, i};
ii get = {p.size(), -1};
if (vis[p[i]] == 0) get = dfs(p, vis, p[i]);
dp[i] = {min(get.first, ans.first), max(get.second, ans.second)};
return dp[i];
}
ii dp3[maxn][maxn];
ii get(vector<int> const& p, vector<int>& vis, int l, int r) {
if (dp3[l][r] != ii{-1, -1}) return dp3[l][r];
if (l == r) return dp3[l][r] = dfs(p, vis, l);
ii h = dfs(p, vis, r);
ii g = get(p, vis, l, r-1);
return dp3[l][r] = {min(g.first, h.first), max(g.second, h.second)};
}
int dp2[maxn][maxn];
int solve(vector<int> const& p, vector<int>& vis, int l, int r, int a, int b) {
if (l < a or r > b) return maxn*maxn;
if (l == a and r == b) return 0;
if (dp2[l][r] != -1) return dp2[l][r];
int& d = dp2[l][r];
d = 0;
if (ii{l, r} != get(p, vis, l, r)) {
ii ps = get(p, vis, l, r);
return dp2[l][r] = solve(p, vis, ps.first, ps.second, a, b);
}
else return dp2[l][r] = min(2 + solve(p, vis, l-1, r, a, b),
2 + solve(p, vis, l, r+1, a, b));
}
long long minimum_walk(std::vector<int> p, int s) {
memset(dp2, -1, sizeof(dp2));
for (int i = 0; i < maxn; i++)
fill(dp3[i], dp3[i]+maxn, ii{-1, -1});
int n = p.size();
ll ans = 0;
int a = s, b = s;
for (int i = 0; i < n; i++) {
if (p[i] != i) a = min(a, i), b = max(b, i);
}
for (int i = 0; i < n; i++) ans += abs(i-p[i]);
vector<int> vis(n);
ans += solve(p, vis, s, s, a, b);
return ans;
}
Compilation message
simurgh.cpp:1:10: fatal error: books.h: No such file or directory
#include "books.h"
^~~~~~~~~
compilation terminated.
