Submission #598723

#TimeUsernameProblemLanguageResultExecution timeMemory
598723piOOERope (JOI17_rope)C++17
45 / 100
2575 ms3840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 100000, M = 10; int a[N], ans[M]; int pref[2][2][N], suf[2][2][N]; // {first or second, left or right} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); memset(ans, 0x3f, sizeof(ans)); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> a[i]; --a[i]; } for (int c1 = 0; c1 < m; ++c1) { for (int c2 = 0; c2 < m; ++c2) { int c[2] = {c1, c2}; pref[0][0][0] = pref[0][1][0] = a[0] != c[0]; pref[1][0][0] = pref[1][1][0] = a[0] != c[1]; for (int i = 1; i < n; ++i) { pref[1][1][i] = (a[i] != c[1]) + pref[1][0][i - 1]; pref[1][0][i] = (a[i] != c[1]) + min(pref[1][1][i - 1], pref[0][0][i - 1]); pref[0][1][i] = (a[i] != c[0]) + min(pref[0][0][i - 1], pref[1][1][i - 1]); pref[0][0][i] = (a[i] != c[0]) + pref[0][1][i - 1]; } suf[0][0][n - 1] = suf[0][1][n - 1] = a[n - 1] != c[0]; suf[1][0][n - 1] = suf[1][1][n - 1] = a[n - 1] != c[1]; for (int i = n - 2; i > -1; --i) { suf[1][1][i] = (a[i] != c[1]) + suf[1][0][i + 1]; suf[1][0][i] = (a[i] != c[1]) + min(suf[1][1][i + 1], suf[0][0][i + 1]); suf[0][1][i] = (a[i] != c[0]) + min(suf[0][0][i + 1], suf[1][1][i + 1]); suf[0][0][i] = (a[i] != c[0]) + suf[0][1][i + 1]; } for (int i = 0; i < n - 1; ++i) { int now = pref[0][0][i] + suf[1][1][i + 1]; ans[c1] = min(ans[c1], now); ans[c2] = min(ans[c2], now); } } } 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...