#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define sp " "
#define N 405
int dp[N][N][N][4];
vector<array<int, 3>> r, g, y;
int n;
const int INF = 1e9 + 7;
int f(int i, int j, int k, int last)
{
int t1 = INF, t2 = INF, t3 = INF;
int pos = i + j + k + 1;
if (pos > n) return 0;
if (dp[i][j][k][last] != -1) return dp[i][j][k][last];
if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
int res = min(t1, t2);
res = min(res, t3);
res = min(res, INF);
return dp[i][j][k][last] = res;
}
void print(int i ,int j, int k, int last)
{
int t1 = INF, t2 = INF, t3 = INF;
int pos = i + j + k + 1;
if (pos > n) return;
if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
if (t1 == f(i, j, k, last))
{
cout<<0;
print(i + 1, j, k, 0);
return;
}
if (t2 == f(i, j, k, last))
{
cout<<1;
print(i, j + 1, k, 1);
return;
}
cout<<2;
print(i, j, k + 1, 2);
}
int32_t main()
{
fastio();
cin>>n;
for (int i = 1; i <= n; i++)
{
char tmp;
cin>>tmp;
if (tmp == 'R') r.pb({(int)r.size(), (int)g.size(), (int)y.size()});
else if (tmp == 'G') g.pb({(int)r.size(), (int)g.size(), (int)y.size()});
else y.pb({(int)r.size(), (int)g.size(), (int)y.size()});
}
for (int i = 0; i <= r.size() + 5; i++)
{
for (int j = 0; j <= g.size() + 5; j++)
{
for (int k = 0; k <= y.size() + 5; k++)
{
for (int last = 0; last <= 3; last++) dp[i][j][k][last] = -1;
}
}
}
int ans = f(0, 0, 0, 3);
if (ans >= INF) cout<<-1<<endl;
else cout<<ans<<endl;
print(0, 0, 0, 3);
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
Compilation message
joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp:28:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void print(int, int, int, int)':
joi2019_ho_t3.cpp:42:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp:43:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp:44:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp:39:26: warning: variable 't3' set but not used [-Wunused-but-set-variable]
39 | int t1 = INF, t2 = INF, t3 = INF;
| ^~
joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i <= r.size() + 5; i++)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j = 0; j <= g.size() + 5; j++)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int k = 0; k <= y.size() + 5; k++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
