oj.uz

Submission #444188

# Submission time Handle Problem Language Result Execution time Memory
444188 2021-07-13T09:51:40 Z nonsensenonsense1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 348 ms 757504 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>

const int INF = 0x3f3f3f3f;

const int N = 401;
int n, amt[3], pos[3][N], d[N][N][N][3];
char s[N];

int f(int last) 
{
	int &cur = d[amt[0]][amt[1]][amt[2]][last];
	if (cur == -1) {
		cur = INF;
		if (!(amt[0] + amt[1] + amt[2])) cur = 0;
		else for (int i = 0; i < 3; ++i) if (i != last && amt[i]) {
			--amt[i];
			cur = std::min(cur, f(i) + abs(amt[0] + amt[1] + amt[2] - pos[i][amt[i]]));
			++amt[i];
		}
	}
	return cur;
}

int main() 
{
	memset(***d, -1, N * N * N * 3 << 2);
	scanf("%d%s", &n, s);
	for (int i = 0; i < n; ++i) {
		int cur;
		if (s[i] == 'R') cur = 0;
		else if (s[i] == 'G') cur = 1;
		else cur = 2;
		pos[cur][amt[cur]++] = i;
	}
	int ans = INF;
	for (int i = 0; i < 3; ++i) ans = std::min(ans, f(i));
	if (ans == INF) printf("-1\n");
	else printf("%d\n", ans >> 1);
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%s", &n, s);
      |  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 757280 KB Output is correct
2 Correct 331 ms 757268 KB Output is correct
3 Correct 334 ms 757312 KB Output is correct
4 Correct 340 ms 757320 KB Output is correct
5 Correct 348 ms 757340 KB Output is correct
6 Correct 339 ms 757504 KB Output is correct
7 Correct 344 ms 757316 KB Output is correct
8 Correct 334 ms 757304 KB Output is correct
9 Correct 329 ms 757332 KB Output is correct
10 Correct 326 ms 757340 KB Output is correct
11 Incorrect 329 ms 757444 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 757280 KB Output is correct
2 Correct 331 ms 757268 KB Output is correct
3 Correct 334 ms 757312 KB Output is correct
4 Correct 340 ms 757320 KB Output is correct
5 Correct 348 ms 757340 KB Output is correct
6 Correct 339 ms 757504 KB Output is correct
7 Correct 344 ms 757316 KB Output is correct
8 Correct 334 ms 757304 KB Output is correct
9 Correct 329 ms 757332 KB Output is correct
10 Correct 326 ms 757340 KB Output is correct
11 Incorrect 329 ms 757444 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 757372 KB Output is correct
2 Correct 324 ms 757440 KB Output is correct
3 Correct 331 ms 757316 KB Output is correct
4 Correct 327 ms 757340 KB Output is correct
5 Correct 339 ms 757308 KB Output is correct
6 Correct 328 ms 757332 KB Output is correct
7 Correct 347 ms 757368 KB Output is correct
8 Correct 330 ms 757384 KB Output is correct
9 Correct 326 ms 757348 KB Output is correct
10 Correct 330 ms 757296 KB Output is correct
11 Correct 328 ms 757372 KB Output is correct
12 Correct 329 ms 757452 KB Output is correct
13 Correct 327 ms 757316 KB Output is correct
14 Correct 347 ms 757404 KB Output is correct
15 Correct 338 ms 757316 KB Output is correct
16 Correct 332 ms 757332 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 757280 KB Output is correct
2 Correct 331 ms 757268 KB Output is correct
3 Correct 334 ms 757312 KB Output is correct
4 Correct 340 ms 757320 KB Output is correct
5 Correct 348 ms 757340 KB Output is correct
6 Correct 339 ms 757504 KB Output is correct
7 Correct 344 ms 757316 KB Output is correct
8 Correct 334 ms 757304 KB Output is correct
9 Correct 329 ms 757332 KB Output is correct
10 Correct 326 ms 757340 KB Output is correct
11 Incorrect 329 ms 757444 KB Output isn't correct
12 Halted 0 ms 0 KB -