| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 929020 | salmon | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++14 | 0 ms | 0 KiB |
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;
int N;
int memo[3][410][410][410];
int rp[410],gp[410],yp[410];
int R;
int G;
int Y;
char lst[410];
const int inf = 1100100100;
bool visited[410];
int root[3][410];
int main(){
scanf(" %d",&N);
for(int i = 0; i < N; i++){
scanf(" %c",&lst[i]);
if(lst[i] == 'R'){
R++;
}
else if(lst[i] == 'G'){
G++;
}
else if(lst[i] == 'Y'){
Y++;
}
}
memo[0][R][G][Y] = 0;
memo[1][R][G][Y] = 0;
memo[2][R][G][Y] = 0;
int it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'R'){
rp[it] = i;
it++;
}
}
it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'G'){
gp[it] = i;
it++;
}
}
it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'Y'){
yp[it] = i;
it++;
}
}
for(int i = 0; i <= N; i++){
root[0][R][i] = 0;
root[0][G][i] = 0;
root[0][Y][i] = 0;
}
for(int r = R - 1; r >= 0; r--){
for(int i = 0; i <= N; i++){
root[0][r][i] = root[0][r + 1][i];
if(i >= rp[r]) root[0][r][i]++;
}
}
for(int g = G - 1; g >= 0; g--){
for(int i = 0; i <= N; i++){
root[1][g][i] = root[1][g + 1][i];
if(i >= gp[g]) root[1][g][i]++;
}
}
for(int y = Y - 1; y >= 0; y--){
for(int i = 0; i <= N; i++){
root[2][y][i] = root[2][y + 1][i];
if(i >= yp[y]) root[2][y][i]++;
}
}
for(int i = N - 1; i >= 0; i--){
for(int r = 0; r <= min(R,i); r++){
for(int g = 0; g <= min(G,i - r); g++){
y = i - r - g;
int j = r + g + y;
if(r == R || min(memo[1][r + 1][g][y], memo[2][r + 1][g][y]) == inf){
memo[0][r][g][y] = inf;
}
else{
memo[0][r][g][y] = min(memo[1][r + 1][g][y], memo[2][r + 1][g][y]) + j-rp[r]+root[0][r+1][rp[r]] + root[1][g][rp[r]] + root[2][y][rp[r]];
}
if(g == G || min(memo[0][r][g + 1][y], memo[2][r][g + 1][y]) == inf){
memo[1][r][g][y] = inf;
}
else{
memo[1][r][g][y] = min(memo[0][r][g + 1][y], memo[2][r][g + 1][y])+ j-gp[g]+root[0][r][gp[g]] + root[1][g+1][gp[g]] + root[2][y][gp[g]];
}
if(y == Y || min(memo[0][r][g][y + 1], memo[1][r][g][y + 1]) == inf){
memo[2][r][g][y] = inf;
}
else{
memo[2][r][g][y] = min(memo[0][r][g][y + 1], memo[1][r][g][y + 1])+ j-yp[y]+root[0][r][yp[y]] + root[1][g][yp[y]] + root[2][y+1][yp[y]];
}
}
}
}
if(min(memo[0][0][0][0],min(memo[1][0][0][0],memo[2][0][0][0])) != inf){
printf("%d",min(memo[0][0][0][0],min(memo[1][0][0][0],memo[2][0][0][0])));
}
else{
printf("-1");
}
}
/*
6
GGGGRRR
GRGRGRG
RGRGYG
*/