Submission #121316

#	Time	Username	Problem	Language	Result	Execution time	Memory
121316		onjo0127	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	0 / 100	1099 ms	319724 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 1e18;
char S[100009], C[4] = "RGY";
vector<int> T[3];
int P[3][100009];
long long D[409][409][409][3];

inline int its(int cn, int cc, int id) {
	return max(0, cc - P[cn][id]);
}

long long go(int r, int g, int y, int x) {
	if(r+g+y == 0) return 0;
	long long &ret = D[r][g][y][x];
	if(ret != -1) return ret;
	ret = INF;
	if(r && x == 0) ret = min(ret, min(go(r-1, g, y, 1), go(r-1, g, y, 2)) + its(1, g, T[0][r-1]) + its(2, y, T[0][r-1]));
	if(g && x == 1) ret = min(ret, min(go(r, g-1, y, 0), go(r, g-1, y, 2)) + its(0, r, T[1][g-1]) + its(2, y, T[1][g-1]));
	if(y && x == 2) ret = min(ret, min(go(r, g, y-1, 0), go(r, g, y-1, 1)) + its(0, r, T[2][y-1]) + its(1, g, T[2][y-1]));
	return ret;
}

int main() {
	int N; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf(" %c",&S[i]);
		for(int j=0; j<3; j++) if(S[i] == C[j]) T[j].push_back(i);
	}
	for(int i=1; i<=N; i++) for(int j=0; j<3; j++) P[j][i] = P[j][i-1] + (S[i] == C[j]);
	memset(D, -1, sizeof(D));
	long long ans = INF;
	for(int i=0; i<3; i++) if(P[i][N]) ans = min(ans, go(P[0][N], P[1][N], P[2][N], i));
	if(ans == INF) puts("-1");
	else printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&S[i]);
   ~~~~~^~~~~~~~~~~~~

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