oj.uz

Submission #428287

# Submission time Handle Problem Language Result Execution time Memory
428287 2021-06-15T09:39:54 Z Berted Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 332 ms 7876 KB 
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const ll INF = 1e18;

int N; string S;
vector<int> A[3];
ll DP[2][3][401][401];

int main()
{
	cin >> N >> S;
	for (int i = 1; i <= N; i++)
	{
		if (S[i - 1] == 'R') {A[0].push_back(i);}
		else if (S[i - 1] == 'G') {A[1].push_back(i);}
		else {A[2].push_back(i);}
	}

	for (int s = 0; s < 3; s++)
		for (int i = 0; i <= N; i++)
			for (int j = 0; j <= N; j++) DP[0][s][i][j] = INF;

	for (int s = 0; s < 3; s++) DP[0][s][0][0] = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int s = 0; s < 3; s++)
			for (int j = 0; j <= N; j++)
				for (int k = 0; k <= N; k++) DP[i & 1][s][j][k] = INF;

		for (int s = 0; s < 3; s++)
		{
			for (int j = 0; j <= i && j <= A[0].size(); j++)
			{
				for (int k = 0; k + j <= i && k <= A[1].size(); k++)
				{
					int l = i - j - k;
					if (l > A[2].size()) continue;

					if (s == 0 && j) 
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j - 1][k] + max(0, A[s][j - 1] - i));
						}
					}

					if (s == 1 && k)
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k - 1] + max(0, A[s][k - 1] - i));
						}
					}

					if (s == 2 && l)
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k] + max(0, A[s][l - 1] - i));
						}
					}

					//if (DP[i & 1][s][j][k] < INF) cout << i << " " << s << " " << j << " " << k << " " << l << " " << DP[i & 1][s][j][k] << "\n";
				}
			}
		}
	}

	ll res = INF;
	for (int s = 0; s < 3; s++) {res = min(res, DP[N & 1][s][A[0].size()][A[1].size()]);}

	if (res == INF) cout << "-1\n";
	else 
	{
		cout << res << "\n";
	}
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:36:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int j = 0; j <= i && j <= A[0].size(); j++)
      |                              ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int k = 0; k + j <= i && k <= A[1].size(); k++)
      |                                   ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |      if (l > A[2].size()) continue;
      |          ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Incorrect 1 ms 560 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Incorrect 1 ms 560 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 1 ms 332 KB Output is correct
2 Correct 317 ms 7828 KB Output is correct
3 Correct 268 ms 7756 KB Output is correct
4 Correct 266 ms 7840 KB Output is correct
5 Correct 275 ms 7876 KB Output is correct
6 Correct 269 ms 7828 KB Output is correct
7 Correct 324 ms 7748 KB Output is correct
8 Correct 265 ms 7844 KB Output is correct
9 Correct 323 ms 7824 KB Output is correct
10 Correct 281 ms 7844 KB Output is correct
11 Correct 286 ms 7756 KB Output is correct
12 Correct 39 ms 4172 KB Output is correct
13 Correct 95 ms 5572 KB Output is correct
14 Correct 183 ms 6536 KB Output is correct
15 Correct 332 ms 7836 KB Output is correct
16 Correct 282 ms 7832 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Incorrect 1 ms 560 KB Output isn't correct
12 Halted 0 ms 0 KB -