Submission #670360

#	Time	Username	Problem	Language	Result	Execution time	Memory
670360		dozer	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1 ms	468 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<array<int, 3>> 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) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
	if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
	if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);

	int res = min(t1, t2);
	res = min(res, t3);
	res = min(res, INF);
	return dp[i][j][k][last] = res;
}


void print(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;
	if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
	if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
	if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
	if (t1 == f(i, j, k, last))
	{
		cout<<0;
		print(i + 1, j, k, 0);
		return;
	}
	if (t2 == f(i, j, k, last))
	{
		cout<<1;
		print(i, j + 1, k, 1);
		return;
	}
	cout<<2;
	print(i, j, k + 1, 2);
}

int32_t main()
{
	fastio();

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

	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<<endl;
	print(0, 0, 0, 3);
	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:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:28:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void print(int, int, int, int)':
joi2019_ho_t3.cpp:42:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  if (i < r.size() && last != 0) t1 = f(i + 1, j, k, 0) + max(0, j - r[i][1]) + max(0, k - r[i][2]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:43:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  if (j < g.size() && last != 1) t2 = f(i, j + 1, k, 1) + max(0, i - g[j][0]) + max(0, k - g[j][2]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:44:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  if (k < y.size() && last != 2) t3 = f(i, j, k + 1, 2) + max(0, i - y[k][0]) + max(0, j - y[k][1]);
      |      ~~^~~~~~~~~~
joi2019_ho_t3.cpp:39:26: warning: variable 't3' set but not used [-Wunused-but-set-variable]
   39 |  int t1 = INF, t2 = INF, t3 = INF;
      |                          ^~
joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i <= r.size() + 5; i++)
      |                  ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int j = 0; j <= g.size() + 5; j++)
      |                   ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for (int k = 0; k <= y.size() + 5; k++)
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25