oj.uz

Submission #121316

# Submission time Handle Problem Language Result Execution time Memory
121316 2019-06-26T10:19:04 Z onjo0127 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++11
0 / 100
 500 ms 319724 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 256508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 256508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 319724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 256508 KB Time limit exceeded
2 Halted 0 ms 0 KB -