oj.uz

Submission #670328

# Submission time Handle Problem Language Result Execution time Memory
670328 2022-12-08T17:07:42 Z dozer Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 5 ms 8148 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define sp " "
#define N 405

int dp[N][N][N][4];
vector<int> r, g, y;
int n;

const int INF = 1e9 + 7;

int f(int i, int j, int k, int last)
{
	int t1 = INF, t2 = INF, t3 = INF;
	int pos = i + j + k + 1;
	if (pos > n) return 0;
	if (dp[i][j][k][last] != -1) return dp[i][j][k][last];
	if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + abs(r[i] - pos);
	if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + abs(g[j] - pos);
	if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + abs(y[k] - pos);
	int res = min(t1, t2);
	res = min(res, t3);
	res = min(res, INF);
	return dp[i][j][k][last] = res;
}

int32_t main()
{
	fastio();

	cin>>n;
	for (int i = 1; i <= n; i++)
	{
		char tmp;
		cin>>tmp;
		if (tmp == 'Y') r.pb(i);
		else if (tmp == 'G') y.pb(i);
		else g.pb(i);
	}

	for (int i = 0; i <= r.size() + 5; i++)
	{
		for (int j = 0; j <= g.size() + 5; j++)
		{
			for (int k = 0; k <= y.size() + 5; k++)
			{
				for (int last = 0; last <= 3; last++) dp[i][j][k][last] = -1;
			}
		}
	}
	int ans = f(0, 0, 0, 3);
	if (ans >= INF) cout<<-1<<endl;
	else cout<<ans / 2<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:25:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + abs(r[i] - pos);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + abs(g[j] - pos);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + abs(y[k] - pos);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i <= r.size() + 5; i++)
      |                  ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int j = 0; j <= g.size() + 5; j++)
      |                   ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for (int k = 0; k <= y.size() + 5; k++)
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 712 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 712 KB Output is correct
11 Incorrect 1 ms 724 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 712 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 712 KB Output is correct
11 Incorrect 1 ms 724 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 468 KB Output is correct
2 Correct 4 ms 8144 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 4 ms 8080 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 3 ms 8148 KB Output is correct
12 Correct 2 ms 4052 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 ms 6868 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 3 ms 8148 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 712 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 712 KB Output is correct
11 Incorrect 1 ms 724 KB Output isn't correct
12 Halted 0 ms 0 KB -