Submission #831480

#TimeUsernameProblemLanguageResultExecution timeMemory
831480maomao90Giraffes (JOI22_giraffes)C++17
32 / 100
18 ms368 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 8005; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); int n; int p[MAXN]; //int dp[MAXN][MAXN][MAXN]; viii pdp, ndp, tdp; int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n; REP (i, 1, n + 1) { cin >> p[i]; p[i]--; } /* iota(p + 1, p + n + 1, 0); shuffle(p + 1, p + n + 1, rnd); */ pdp.pb({1, n, 0}); REP (x, 0, n + 1) { ndp.clear(); cerr << x << ": " << SZ(pdp) << '\n'; REP (l, 1, n + 1) { // p[l] is min int r = -INF; for (auto [pl, pr, pmn] : pdp) { if (l < pl || l > pr) { continue; } int pmx = pmn + pr - pl; if (p[l] < pmn || p[l] > pmx) { continue; } int tr = pr - max(0, p[l] - pmn - (l - pl)); mxto(r, tr); } if (r != -INF) { ndp.pb({l + 1, r, p[l] + 1}); } } REP (l, 1, n + 1) { // p[l] is max int r = -INF; for (auto [pl, pr, pmn] : pdp) { if (l < pl || l > pr) { continue; } int pmx = pmn + pr - pl; if (p[l] < pmn || p[l] > pmx) { continue; } int tr = pr - max(0, pmx - p[l] - (l - pl)); mxto(r, tr); } if (r != -INF) { ndp.pb({l + 1, r, p[l] - (r - l)}); } } REP (r, 1, n + 1) { // p[r] is min int l = INF; for (auto [pl, pr, pmn] : pdp) { if (r < pl || r > pr) { continue; } int pmx = pmn + pr - pl; if (p[r] < pmn || p[r] > pmx) { continue; } int tl = pl + max(0, p[r] - pmn - (pr - r)); mnto(l, tl); } if (l != INF) { ndp.pb({l, r - 1, p[r] + 1}); } } REP (r, 1, n + 1) { // p[r] is max int l = INF; for (auto [pl, pr, pmn] : pdp) { if (r < pl || r > pr) { continue; } int pmx = pmn + pr - pl; if (p[r] < pmn || p[r] > pmx) { continue; } int tl = pl + max(0, pmx - p[r] - (pr - r)); mnto(l, tl); } if (l != INF) { ndp.pb({l, r - 1, p[r] - (r - l)}); } } if (ndp.empty()) { cout << n - x << '\n'; return 0; } tdp.clear(); sort(ALL(ndp)); for (auto [l, r, mn] : ndp) { if (!tdp.empty() && get<1>(tdp.back()) > r) { continue; } tdp.pb({l, r, mn}); } pdp = tdp; } /* RREP (l, n, 1) { REP (r, l, n + 1) { REP (mn, 0, n) { int mx = mn + (r - l); dp[l][r][mn] = max({ dp[l + 1][r][mn + 1] + (p[l] == mn), dp[l + 1][r][mn] + (p[l] == mx), dp[l][r - 1][mn + 1] + (p[r] == mn), dp[l][r - 1][mn] + (p[r] == mx)}); } } } cout << n - dp[1][n][0] << '\n'; */ return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...