oj.uz

Submission #444181

# Submission time Handle Problem Language Result Execution time Memory
444181 2021-07-13T09:37:20 Z nonsensenonsense1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 357 ms 757460 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 if (2 * std::max(amt[0], std::max(amt[1], amt[2])) <= amt[0] + amt[1] + amt[2] + 1) 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 348 ms 757440 KB Output is correct
2 Correct 330 ms 757320 KB Output is correct
3 Correct 340 ms 757304 KB Output is correct
4 Correct 326 ms 757288 KB Output is correct
5 Correct 329 ms 757360 KB Output is correct
6 Correct 333 ms 757440 KB Output is correct
7 Correct 352 ms 757376 KB Output is correct
8 Correct 335 ms 757264 KB Output is correct
9 Correct 332 ms 757316 KB Output is correct
10 Correct 333 ms 757304 KB Output is correct
11 Incorrect 338 ms 757268 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 757440 KB Output is correct
2 Correct 330 ms 757320 KB Output is correct
3 Correct 340 ms 757304 KB Output is correct
4 Correct 326 ms 757288 KB Output is correct
5 Correct 329 ms 757360 KB Output is correct
6 Correct 333 ms 757440 KB Output is correct
7 Correct 352 ms 757376 KB Output is correct
8 Correct 335 ms 757264 KB Output is correct
9 Correct 332 ms 757316 KB Output is correct
10 Correct 333 ms 757304 KB Output is correct
11 Incorrect 338 ms 757268 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 340 ms 757316 KB Output is correct
2 Correct 325 ms 757460 KB Output is correct
3 Correct 336 ms 757360 KB Output is correct
4 Correct 332 ms 757408 KB Output is correct
5 Correct 328 ms 757316 KB Output is correct
6 Correct 332 ms 757404 KB Output is correct
7 Correct 353 ms 757316 KB Output is correct
8 Correct 339 ms 757408 KB Output is correct
9 Correct 337 ms 757396 KB Output is correct
10 Correct 330 ms 757320 KB Output is correct
11 Correct 327 ms 757452 KB Output is correct
12 Correct 326 ms 757368 KB Output is correct
13 Correct 332 ms 757384 KB Output is correct
14 Correct 333 ms 757292 KB Output is correct
15 Correct 331 ms 757368 KB Output is correct
16 Correct 357 ms 757352 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 757440 KB Output is correct
2 Correct 330 ms 757320 KB Output is correct
3 Correct 340 ms 757304 KB Output is correct
4 Correct 326 ms 757288 KB Output is correct
5 Correct 329 ms 757360 KB Output is correct
6 Correct 333 ms 757440 KB Output is correct
7 Correct 352 ms 757376 KB Output is correct
8 Correct 335 ms 757264 KB Output is correct
9 Correct 332 ms 757316 KB Output is correct
10 Correct 333 ms 757304 KB Output is correct
11 Incorrect 338 ms 757268 KB Output isn't correct
12 Halted 0 ms 0 KB -