oj.uz

Submission #909820

# Submission time Handle Problem Language Result Execution time Memory
909820 2024-01-17T12:55:26 Z OAleksa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
20 / 100
 117 ms 612696 KB 
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 410;
const int inf = 1e9 + 69;
int dp[N][N][N][3], n, pr[3][N];
string s;
vector<int> pos[3];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> s;
  	int a = 0, b = 0, c = 0;
  	for (int i = 0;i < n;i++) {
  		if (s[i] == 'R')
  			s[i] = 'A';
  		else if (s[i] == 'G')
  			s[i] = 'B';
  		else
  			s[i] = 'C';
  		a += (s[i] == 'A');
  		b += (s[i] == 'B');
  		c += (s[i] == 'C');
  		pos[s[i] - 'A'].push_back(i);
  	}
  	for (int i = 0;i < n;i++) {
  		if (i > 0) {
				pr[0][i] += pr[0][i - 1];
  			pr[1][i] += pr[1][i - 1];
  			pr[2][i] += pr[2][i - 1]; 
  		}
  		pr[0][i] += (s[i] == 'A');
  		pr[1][i] += (s[i] == 'B');
  		pr[2][i] += (s[i] == 'C');
  	}
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++)
  				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
  		}
  	}
  	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  	auto C = [&](int L, int R) {
  		if (L == 0)
  			return pr[2][R];
  		else if (R < L)
  			return 0ll;
  		return pr[2][R] - pr[2][L - 1];
  	};
  	auto B = [&](int L, int R) {
  		if (L == 0)
  			return pr[1][R];
  		else if (R < L)
  			return 0ll;
  		return pr[1][R] - pr[1][L - 1];
  	};
  	auto A = [&](int L, int R) {
  		if (L == 0)
  			return pr[0][R];
  		else if (R < L)
  			return 0ll;
  		return pr[0][R] - pr[0][L - 1];
  	};
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++) {
  				int p = i + j + k - 1;
  				if (i > 0) {
  					int L = p, R = pos[0][i - 1] + 1;
  					int p1 = 0, p2 = 0;
  					if (j > 0)
  						p1 = pos[1][j - 1];
  					if (k > 0)
  						p2 = pos[2][k - 1];
  					if (R <= L)
  						dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]);
  					else
  						dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + (R - 1 + C(R, p2) + B(R, p1) - L);
  				}
  				if (j > 0) {
  					int L = p, R = pos[1][j - 1] + 1;
  					int p1 = 0, p2 = 0;
  					if (i > 0)
  						p1 = pos[0][i - 1];
  					if (k > 0)
  						p2 = pos[2][k - 1];
  					if (R <= L)
  						dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]);
  					else
  						dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + (R - 1 + A(R, p1) + C(R, p2) - L);
  				}
  				if (k > 0) {
  					int L = p, R = pos[2][k - 1] + 1;
  					int p1 = 0, p2 = 0;
  					if (i > 0)
  						p1 = pos[0][i - 1];
  					if (j > 0)
  						p2 = pos[1][j - 1];
  					if (R <= L)
  						dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]);
  					else
  						dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]) + (R - 1 + A(R, p1) + B(R, p2) - L);
  				}
  			}
  		}
  	}
  	int ans = inf;
  	for (int i = 0;i < 3;i++)
  		ans = min(ans, dp[a][b][c][i]);
  	if (ans >= inf)	
  		ans = -1;
  	cout << ans;
	}
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14836 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 4 ms 20840 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 4 ms 23016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14836 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 4 ms 20840 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 4 ms 23016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 8 ms 51804 KB Output is correct
19 Correct 6 ms 41564 KB Output is correct
20 Correct 9 ms 53852 KB Output is correct
21 Correct 7 ms 45656 KB Output is correct
22 Correct 8 ms 49752 KB Output is correct
23 Correct 7 ms 39516 KB Output is correct
24 Correct 5 ms 22876 KB Output is correct
25 Correct 12 ms 82572 KB Output is correct
26 Correct 11 ms 70232 KB Output is correct
27 Correct 10 ms 62084 KB Output is correct
28 Correct 8 ms 47708 KB Output is correct
29 Correct 8 ms 49756 KB Output is correct
30 Correct 7 ms 39516 KB Output is correct
31 Correct 6 ms 35284 KB Output is correct
32 Correct 7 ms 41564 KB Output is correct
33 Correct 9 ms 57904 KB Output is correct
34 Correct 7 ms 52068 KB Output is correct
35 Correct 8 ms 51684 KB Output is correct
36 Incorrect 7 ms 43612 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 96 ms 473432 KB Output is correct
3 Correct 92 ms 508928 KB Output is correct
4 Correct 100 ms 514388 KB Output is correct
5 Correct 100 ms 502772 KB Output is correct
6 Correct 98 ms 501284 KB Output is correct
7 Correct 103 ms 522060 KB Output is correct
8 Correct 97 ms 536156 KB Output is correct
9 Correct 107 ms 539180 KB Output is correct
10 Correct 117 ms 576864 KB Output is correct
11 Correct 105 ms 590664 KB Output is correct
12 Correct 42 ms 312420 KB Output is correct
13 Correct 67 ms 468340 KB Output is correct
14 Correct 84 ms 567288 KB Output is correct
15 Correct 105 ms 612696 KB Output is correct
16 Correct 102 ms 612696 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14836 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 4 ms 20840 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 4 ms 23016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 8 ms 51804 KB Output is correct
19 Correct 6 ms 41564 KB Output is correct
20 Correct 9 ms 53852 KB Output is correct
21 Correct 7 ms 45656 KB Output is correct
22 Correct 8 ms 49752 KB Output is correct
23 Correct 7 ms 39516 KB Output is correct
24 Correct 5 ms 22876 KB Output is correct
25 Correct 12 ms 82572 KB Output is correct
26 Correct 11 ms 70232 KB Output is correct
27 Correct 10 ms 62084 KB Output is correct
28 Correct 8 ms 47708 KB Output is correct
29 Correct 8 ms 49756 KB Output is correct
30 Correct 7 ms 39516 KB Output is correct
31 Correct 6 ms 35284 KB Output is correct
32 Correct 7 ms 41564 KB Output is correct
33 Correct 9 ms 57904 KB Output is correct
34 Correct 7 ms 52068 KB Output is correct
35 Correct 8 ms 51684 KB Output is correct
36 Incorrect 7 ms 43612 KB Output isn't correct
37 Halted 0 ms 0 KB -