Submission #831344

#TimeUsernameProblemLanguageResultExecution timeMemory
831344maomao90Giraffes (JOI22_giraffes)C++17
32 / 100
40 ms2980 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 = 13; int n; int p[MAXN + 5]; int dp[MAXN + 5][MAXN + 5][1 << MAXN]; 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]--; } dp[n + 1][n][0] = 0; RREP (l, n, 1) { dp[l][l - 1][0] = 0; REP (r, l, n + 1) { REP (msk, 0, 1 << n) { int pop = 0, mn = INF, mx = -INF; REP (i, 0, n) { if (msk >> i & 1) { mnto(mn, i); mxto(mx, i); pop++; } } if (pop != r - l + 1) { continue; } dp[l][r][msk] = min({ dp[l + 1][r][msk ^ (1 << mn)] + (p[l] != mn), dp[l + 1][r][msk ^ (1 << mx)] + (p[l] != mx), dp[l][r - 1][msk ^ (1 << mn)] + (p[r] != mn), dp[l][r - 1][msk ^ (1 << mx)] + (p[r] != mx)}); } } } cout << dp[1][n][(1 << n) - 1] << '\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...