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;
#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
} return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
} return false;
}
template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
static_assert(dimension > 0, "Dimension must be positive !\n");
template<typename... Args>
tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};
template<typename T>
struct tensor<1, T> : public vector<T> {
tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};
const int MAX = 405;
int n, num[3], cnt[3][MAX], pos[3][MAX], dp[3][MAX][MAX][MAX];
string s;
int count(int i, int l, int r){
if(l > r) return 0;
return cnt[i][r] - cnt[i][l];
}
int find_other(int a, int b){
if(a > b) swap(a, b);
if(a > 0) return 0;
if(b < 2) return 2;
return 1;
}
void relable(string& s){
int r = 0, g = 0, y = 0;
for(int i = 0; i < sz(s); ++i){
r += (s[i] == 'R');
g += (s[i] == 'G');
y += (s[i] == 'Y');
}
vector<pair<int, int>> pts;
pts.push_back({r, 'R'});
pts.push_back({g, 'G'});
pts.push_back({y, 'Y'});
sort(all(pts));
for(int i = 0; i < sz(s); ++i){
for(int j = 0; j < 3; ++j){
if(s[i] == pts[j].second){
s[i] = j;
break;
}
}
}
}
void testcase(){
cin >> n >> s;
relable(s);
for(int i = 0; i < n; ++i){
pos[s[i]][++num[s[i]]] = i + 1;
for(int j = 0; j < 3; ++j) cnt[j][i + 1] = num[j];
}
memset(dp, 0x3f, sizeof(dp));
int inf = dp[0][0][0][0];
for(int i = 0; i < 3; ++i) dp[i][0][0][0] = 0;
for(int i = 0; i <= num[0]; ++i){
for(int j = 0; j <= num[1]; ++j){
for(int k = 0; k <= num[2]; ++k){
for(int last = 0; last < 3; ++last){
if(dp[last][i][j][k] == inf) continue;
for(int nw = 0; nw < 3; ++nw){
if(last != nw && (nw != 0 || i < num[0]) && (nw != 1 || j < num[1]) && (nw != 2 || k < num[2])){
int oth = find_other(last, nw);
int pos_last = pos[last][(last == 0 ? i : (last == 1 ? j : k))];
int pos_nw = pos[nw][(nw == 0 ? i : (nw == 1 ? j : k)) + 1];
int pos_oth = pos[oth][(oth == 0 ? i : (oth == 1 ? j : k))];
int cost = count(last, pos_last, pos_nw) + count(oth, pos_oth, pos_nw);
minimize(dp[nw][i + (nw == 0)][j + (nw == 1)][k + (nw == 2)], dp[last][i][j][k] + cost);
}
}
}
}
}
}
int ans = inf;
for(int i = 0; i < 3; ++i){
minimize(ans, dp[i][num[0]][num[1]][num[2]]);
}
cout << (ans == inf ? -1 : ans);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
file("task");
int T = 1;
// cin >> T;
while(T--){
testcase();
}
return 0;
}
Compilation message (stderr)
joi2019_ho_t3.cpp: In function 'void testcase()':
joi2019_ho_t3.cpp:90:17: warning: array subscript has type 'char' [-Wchar-subscripts]
90 | pos[s[i]][++num[s[i]]] = i + 1;
| ^
joi2019_ho_t3.cpp:90:29: warning: array subscript has type 'char' [-Wchar-subscripts]
90 | pos[s[i]][++num[s[i]]] = i + 1;
| ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:9:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:130:5: note: in expansion of macro 'file'
130 | file("task");
| ^~~~
joi2019_ho_t3.cpp:9:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:130:5: note: in expansion of macro 'file'
130 | file("task");
| ^~~~
# | 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... |