Submission #97386

#	Time	Username	Problem	Language	Result	Execution time	Memory
97386		Bruteforceman	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	378 ms	194412 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;
int a[444];
int n;
const int inf = 1e9;
int dp[3][405][405][405];
bool vis[405];
int cnt[3][404];
vector <int> col[3];

int main(int argc, char const *argv[])
{
	// memset(mem, -1, sizeof mem);
	scanf("%d", &n);
	char txt[444];
	scanf("%s", txt);
	for(int i = 0; i < n; i++) {
		if(txt[i] == 'R') {
			a[i+1] = 0;
		} else if (txt[i] == 'G') {
			a[i+1] = 1;
		} else {
			a[i+1] = 2;
		}
	}
	col[0].push_back(0);
	col[1].push_back(0);
	col[2].push_back(0);
	for(int i = 1; i <= n; i++) {
		for(int k = 0; k < 3; k++) {
			cnt[k][i] = cnt[k][i - 1];
		}
		cnt[a[i]][i] += 1;
		col[a[i]].push_back(i);
	}
	int R = col[0].size() - 1;
	int B = col[1].size() - 1;
	int G = col[2].size() - 1;

	for(int last = 0; last < 3; last++) {
		for(int r = 0; r <= R; r++) {
			for(int b = 0; b <= B; b++) {
				for(int g = 0; g <= G; g++) {
					dp[last][r][b][g] = inf;
				}
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[1][0][0][0] = 0;
	dp[2][0][0][0] = 0;
	for(int r = 0; r <= R; r++) {
		for(int b = 0; b <= B; b++) {
			for(int g = 0; g <= G; g++) {
				for(int last = 0; last < 3; last++) {
					int ans = dp[last][r][b][g];
					int c[3];
					c[0] = r;
					c[1] = b;
					c[2] = g;
					for(int i = 0; i < 3; i++) {
						if(col[i].size() <= c[i] + 1 || last == i) continue;
						int pos = col[i][c[i] + 1];
						int tot = -1;
						for(int x = 0; x < 3; x++) {
							int prev = col[x][c[x]];
							tot += max(0, cnt[x][pos] - cnt[x][prev]);
						}
						c[i] += 1;
						dp[i][c[0]][c[1]][c[2]] = min(dp[i][c[0]][c[1]][c[2]], tot + ans);
						c[i] -= 1;
					}
				}
			}
		}
	}
	int ans = inf;
	for(int i = 0; i < 3; i++) {
		ans = min(ans, dp[i][R][B][G]);
	}
	printf("%d\n", ans >= inf ? -1 : ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main(int, const char**)':
joi2019_ho_t3.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(col[i].size() <= c[i] + 1 || last == i) continue;
          ~~~~~~~~~~~~~~^~~~~~~~~~~
joi2019_ho_t3.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", txt);
  ~~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25