oj.uz

Submission #670315

# Submission time Handle Problem Language Result Execution time Memory
670315 2022-12-08T16:57:07 Z dozer Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 2 ms 340 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()
{
	fileio();
	fastio();

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

	for (int i = 0; i <= r.size(); i++)
	{
		for (int j = 0; j <= g.size(); j++)
		{
			for (int k = 0; k <= y.size(); 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:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i <= r.size(); i++)
      |                  ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = 0; j <= g.size(); j++)
      |                   ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (int k = 0; k <= y.size(); k++)
      |                    ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:3:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:2: note: in expansion of macro 'fileio'
   36 |  fileio();
      |  ^~~~~~
joi2019_ho_t3.cpp:3:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:2: note: in expansion of macro 'fileio'
   36 |  fileio();
      |  ^~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -