Submission #670328

#	Time	Username	Problem	Language	Result	Execution time	Memory
670328		dozer	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	5 ms	8148 KiB

joi2019_ho_t3

#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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25