Submission #1204936

#TimeUsernameProblemLanguageResultExecution timeMemory
1204936HasanV11010238Ancient Books (IOI17_books)C++20
42 / 100
144 ms23880 KiB
#include "books.h" #include <bits/stdc++.h> #define ll long long #define INF 1000000000000000 using namespace std; vector<int> vis, to, ml, mr; int le, ri; void dfs(int x){ le = min(le, x); ri = max(ri, x); vis[x] = 1; if (vis[to[x]] == 0) dfs(to[x]); } void ass(int x, int va1, int va2){ ml[x] = va1; mr[x] = va2; vis[x] = 2; if (vis[to[x]] == 1) ass(to[x], va1, va2); } long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); ll ans = 0; for (int i = 0; i < n; i++){ ans += abs(i - p[i]); } to = p; vis.assign(n, 0), ml.assign(n, 0), mr.assign(n, 0); for (int i = 0; i < n; i++){ if (vis[i] == 0){ le = n, ri = 0; dfs(i); ass(i, le, ri); } } int l = 0, r = n - 1; while (l < s && to[l] == l) l++; while (r > s && to[r] == r) r--; if (l > r) return 0; if (n <= 1000){ vector<vector<ll>> dp(n, vector<ll>(n, INF)); vector<vector<int>> mi(n, vector<int>(n, n)), ma(n, vector<int>(n, 0)); for (int i = 0; i < n; i++){ mi[i][i] = ml[i], ma[i][i] = mr[i]; for (int j = i + 1; j < n; j++){ mi[i][j] = min(mi[i][j - 1], ml[j]); ma[i][j] = max(ma[i][j - 1], mr[j]); } } dp[s][s] = 0; for (int ga = 0; ga < n; ga++){ for (int i = 0, j = ga; j < n; i++, j++){ dp[mi[i][j]][ma[i][j]] = min(dp[mi[i][j]][ma[i][j]], dp[i][j]); if (i != 0){ dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + 2); } if (j != n - 1){ dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 2); } } } return dp[l][r] + ans; } int tt; for (int i = 0; i < r; i++){ if (tt < i) ans += 2; tt = max(tt, mr[i]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...