Submission #105165

#	Time	Username	Problem	Language	Result	Execution time	Memory
105165		tincamatei	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	126 ms	4172 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 400;
const int INF = 1000000000;

int dp[2][1+MAX_N][1+MAX_N][3];
vector<int> pos[3];

char str[1+MAX_N];

char getchar(FILE *fin) {
	char ch = fgetc(fin);
	while(!isalpha(ch))
		ch = fgetc(fin);
	return ch;
}

void initDp(int p) {
	for(int i = 0; i <= MAX_N; ++i)
		for(int j = 0; j <= MAX_N; ++j)
			for(int k = 0; k < 3; ++k)
				dp[p][i][j][k] = INF;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif
	
	int n;
	fscanf(fin, "%d", &n);

	for(int i = 1; i <= n; ++i) {
		str[i] = getchar(fin);
		if(str[i] == 'R')
			str[i] = 0;
		else if(str[i] == 'G')
			str[i] = 1;
		else
			str[i] = 2;
		
		pos[str[i]].push_back(i);
	}
	
	initDp(0);
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for(int i = 1; i <= n; ++i) {
		int p = i % 2;
		int ind[3];
		initDp(p);
		
		for(ind[0] = 0; ind[0] <= pos[0].size(); ++ind[0])
			for(ind[1] = 0; ind[1] <= pos[1].size(); ++ind[1]) {
				ind[2] = i - ind[0] - ind[1];
				if(0 <= ind[2] && ind[2] <= pos[2].size()) {
					for(int oldblock = 0; oldblock < 3; ++oldblock)
						for(int newblock = 0; newblock < 3; ++newblock) {
							if(oldblock != newblock) {
								int indcp[3];
								for(int x = 0; x < 3; ++x)
									indcp[x] = ind[x];
								
								indcp[newblock]--;
								if(indcp[newblock] >= 0) {
									dp[p][ind[0]][ind[1]][newblock] = min(dp[p][ind[0]][ind[1]][newblock],
										                                    dp[1-p][indcp[0]][indcp[1]][oldblock] + max(0, i - pos[newblock][indcp[newblock]]));
								}
							}
						}
				}
			}
	}
	
	int rez = min(min(dp[n % 2][pos[0].size()][pos[1].size()][0],
	                  dp[n % 2][pos[0].size()][pos[1].size()][1]),
	                  dp[n % 2][pos[0].size()][pos[1].size()][2]);
	
	if(rez >= INF)
		fprintf(fout, "-1");
	else
		fprintf(fout, "%d", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:48:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   pos[str[i]].push_back(i);
             ^
joi2019_ho_t3.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ind[0] = 0; ind[0] <= pos[0].size(); ++ind[0])
                   ~~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ind[1] = 0; ind[1] <= pos[1].size(); ++ind[1]) {
                    ~~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:61:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(0 <= ind[2] && ind[2] <= pos[2].size()) {
                       ~~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~

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