Submission #848929

#TimeUsernameProblemLanguageResultExecution timeMemory
848929qthang2k11NLO (COCI18_nlo)C++17
0 / 110
16 ms65536 KiB
#include <bits/stdc++.h> using namespace std; template<class X, class Y> inline void mini(X &x, Y y) { if (x > y) x = y; } const int N = 404; int sum[N][3], dp[N][N][N][3]; vector<int> pos[3]; string s; int n; inline int get(int c, int l, int r) { return sum[r][c] - sum[l - 1][c]; } int32_t main() { cin.tie(0)->sync_with_stdio(0); map<char, int> mp; mp['R'] = 0; mp['G'] = 1; mp['Y'] = 2; cin >> n >> s; for (int i = 1; i <= n; i++) { int val = mp[s[i - 1]]; for (int j = 0; j < 3; j++) sum[i][j] = sum[i - 1][j]; sum[i][val]++; pos[val].emplace_back(i); } memset(dp, 63, sizeof dp); int INF = dp[0][0][0][0]; vector<int> num; for (int s: {0, 1, 2}) { dp[0][0][0][s] = 0; num.emplace_back((int)pos[s].size()); } vector<int> a(3, 0), p(3, 0); for (a[0] = 0; a[0] <= num[0]; a[0]++) { for (a[1] = 0; a[1] <= num[1]; a[1]++) { for (a[2] = 0; a[2] <= num[2]; a[2]++) { for (int lst = 0; lst < 3; lst++) { int cur = dp[a[0]][a[1]][a[2]][lst]; if (cur == INF) continue; for (int d = 0; d < 3; d++) { if (d == lst || a[d] == num[d]) continue; int now = cur, where = pos[d][a[d]]; for (int i = 0; i < 3; i++) if (d != i) now += max(sum[where][i] - a[i], 0); a[d]++; mini(dp[a[0]][a[1]][a[2]][d], now); a[d]--; } } if (a[2] < num[2]) p[2] = pos[2][a[2]]; } if (a[1] < num[1]) p[1] = pos[1][a[1]]; } if (a[0] < num[0]) p[0] = pos[0][a[0]]; } int ans = INF; for (int i = 0; i < 3; i++) mini(ans, dp[num[0]][num[1]][num[2]][i]); if (ans == INF) cout << -1; else cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...