Submission #598557

#TimeUsernameProblemLanguageResultExecution timeMemory
598557piOOERope (JOI17_rope)C++17
15 / 100
2433 ms468 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; void merge(vector<int> &a, vector<int> &b) { if (a.size() < b.size()) { swap(a, b); } for (int x: b) { a.push_back(x); } b.clear(); } const int N = 15; int a[N], ans[N]; int s, n, m; void rec(int L, int R, vector<vector<int>> g) { if (L == s && R == s + 1) { for (int c1 = 0; c1 < m; ++c1) { for (int c2 = 0; c2 < m; ++c2) { int now = 0; for (int x: g[s]) { now += a[x] != c1; } for (int x: g[s + 1]) { now += a[x] != c2; } ans[c1] = min(ans[c1], now); ans[c2] = min(ans[c2], now); } } return; } for (int i = L + 1; i <= s; ++i) { if (i + (i - L) - 1 > R) { break; } vector nxt(g); for (int j = L; j < i; ++j) { merge(nxt[i + (i - j) - 1], nxt[j]); } rec(i, R, nxt); } for (int i = R - 1; i >= s + 1; --i) { if (i - (R - i) + 1 < s) { break; } vector nxt(g); for (int j = R; j > i; --j) { merge(nxt[i - (j - i) + 1], nxt[j]); } rec(L, i, nxt); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); memset(ans, 0x3f, sizeof(ans)); cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> a[i]; --a[i]; } vector g(n, vector<int>(1)); for (int i = 0; i < n; ++i) { g[i][0] = i; } for (s = 0; s < n - 1; ++s) { rec(0, n - 1, g); } for (int i = 0; i < m; ++i) { cout << ans[i] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...