This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MN = 410;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> va;
typedef vector<va> vb;
typedef vector<vb> vc;
const int INF = 1e9;
struct P {
int pr,pg,py;
};
vc dp;
vi kt[3];
vector<P> po[3];
int main() {
int n;
cin >> n;
string s;
cin >> s;
for(int i=0;i<s.size();i++) {
P pos{int(kt[0].size()),int(kt[1].size()),int(kt[2].size())};
if(s[i] == 'R') {
kt[0].push_back(i);
po[0].push_back(pos);
} else if(s[i] == 'G') {
kt[1].push_back(i);
po[1].push_back(pos);
} else {
kt[2].push_back(i);
po[2].push_back(pos);
}
}
dp.assign(3,vb(kt[0].size()+1,va(kt[1].size()+1,vi(kt[2].size()+1,INF))));
dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
for(int i=0;i<=kt[0].size();i++) {
for(int j=0;j<=kt[1].size();j++) {
for(int k=0;k<=kt[2].size();k++) {
for(int c=0;c<3;c++) {
int cur = dp[c][i][j][k];
if(c != 0 && i < kt[0].size()) {
P pos = po[0][i];
int co = max(0,pos.pg-j) + max(0,pos.py-k);
int& nx = dp[0][i+1][j][k];
nx = min(nx,cur+co);
}
if(c != 1 && j < kt[1].size()) {
P pos = po[1][j];
int co = max(0,pos.pr-i) + max(0,pos.py-k);
int& nx = dp[1][i][j+1][k];
nx = min(nx,cur+co);
}
if(c != 2 && k < kt[2].size()) {
P pos = po[2][k];
int co = max(0,pos.pr-i) + max(0,pos.pg-j);
int& nx = dp[2][i][j][k+1];
nx = min(nx,cur+co);
}
}
}
}
}
int res = INF;
for(int i=0;i<3;i++) {
res = min(res,dp[i][kt[0].size()][kt[1].size()][kt[2].size()]);
}
if(res == INF) {
cout << -1 << '\n';
} else {
cout << res << '\n';
}
}
Compilation message (stderr)
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<s.size();i++) {
| ~^~~~~~~~~
joi2019_ho_t3.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<=kt[0].size();i++) {
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j=0;j<=kt[1].size();j++) {
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int k=0;k<=kt[2].size();k++) {
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if(c != 0 && i < kt[0].size()) {
| ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(c != 1 && j < kt[1].size()) {
| ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if(c != 2 && k < kt[2].size()) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |