Submission #1032530

#TimeUsernameProblemLanguageResultExecution timeMemory
1032530juicyGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
100 / 100
388 ms782272 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 405; int n; string s; int sf[3][N][N], dp[N][N][N][3]; int conv(char c) { return c == 'R' ? 0 : (c == 'G' ? 1 : 2); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> s; array<int, 3> cnt{}; array<vector<int>, 3> pos; for (int i = 0; i < n; ++i) { int c = conv(s[i]); ++cnt[c]; pos[c].push_back(i); } for (int i = 0; i < 3; ++i) { for (int j = 1; j <= n; ++j) { for (int k = cnt[i] - 1; k >= 0; --k) { sf[i][j][k] = sf[i][j][k + 1] + (pos[i][k] < j); } } } memset(dp, 0x3f, sizeof(dp)); for (int j = 0; j < 3; ++j) { dp[0][0][0][j] = 0; } for (int i = 0; i <= cnt[0]; ++i) { for (int j = 0; j <= cnt[1]; ++j) { for (int k = 0; k <= cnt[2]; ++k) { for (int c = 0; c < 3; ++c) { if (dp[i][j][k][c] < 1e9) { auto cost = [&](int p) { return sf[0][p][i] + sf[1][p][j] + sf[2][p][k]; }; if (c != 0 && i + 1 <= cnt[0]) { dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][c] + cost(pos[0][i])); } if (c != 1 && j + 1 <= cnt[1]) { dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][c] + cost(pos[1][j])); } if (c != 2 && k + 1 <= cnt[2]) { dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][c] + cost(pos[2][k])); } } } } } } int res = *min_element(dp[cnt[0]][cnt[1]][cnt[2]], dp[cnt[0]][cnt[1]][cnt[2]] + 3); cout << (res > 1e9 ? -1 : res); 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...