oj.uz

Submission #427957

# Submission time Handle Problem Language Result Execution time Memory
427957 2021-06-15T06:06:21 Z Berted Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 257 ms 7956 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] + abs(i - A[0][j - 1]));
						}
					}

					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] + abs(i - A[1][k - 1]));
						}
					}

					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] + abs(i - A[2][l - 1]));
						}
					}

					//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 / 2 << "\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 560 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 564 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 588 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 560 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 564 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 588 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 203 ms 7836 KB Output is correct
3 Correct 199 ms 7828 KB Output is correct
4 Correct 184 ms 7848 KB Output is correct
5 Correct 179 ms 7844 KB Output is correct
6 Correct 257 ms 7848 KB Output is correct
7 Correct 208 ms 7956 KB Output is correct
8 Correct 172 ms 7828 KB Output is correct
9 Correct 159 ms 7756 KB Output is correct
10 Correct 162 ms 7832 KB Output is correct
11 Correct 161 ms 7872 KB Output is correct
12 Correct 30 ms 4172 KB Output is correct
13 Correct 58 ms 5452 KB Output is correct
14 Correct 119 ms 6476 KB Output is correct
15 Correct 174 ms 7832 KB Output is correct
16 Correct 192 ms 7852 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 560 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 564 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 588 KB Output isn't correct
12 Halted 0 ms 0 KB -