oj.uz

Submission #199064

# Submission time Handle Problem Language Result Execution time Memory
199064 2020-01-29T03:56:23 Z mahmoudbadawy Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 774708 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> pos[3];
int mem[404][404][404][3];
int n;
string s;

int go(int x,int y,int z,int las)
{
	if(x+y+z==n) return 0;
	int &ret=mem[x][y][z][las];
	if(ret!=-1) return ret;
	ret=(1<<30);
	int cpos=x+y+z;
	if(x<pos[0].size()&&(las!=0||cpos==0))
		ret=min(ret,go(x+1,y,z,0)+abs(cpos-pos[0][x]));
	if(y<pos[1].size()&&(las!=1||cpos==0))
		ret=min(ret,go(x,y+1,z,1)+abs(cpos-pos[1][y]));
	if(z<pos[2].size()&&(las!=2||cpos==0))
		ret=min(ret,go(x,y,z+1,2)+abs(cpos-pos[2][z]));
	return ret;
}

int main()
{
	cin >> n >> s;
	memset(mem,-1,sizeof mem);
	for(int i=0;i<n;i++)
	{
		if(s[i]=='R') pos[0].push_back(i);
		else if(s[i]=='G') pos[1].push_back(i);
		else pos[2].push_back(i);
	}
	int ans=go(0,0,0,0);
	if(ans>=(1<<30)) ans=-1;
	else ans/=2;
	cout << ans << endl;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int go(int, int, int, int)':
joi2019_ho_t3.cpp:17:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(x<pos[0].size()&&(las!=0||cpos==0))
     ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(y<pos[1].size()&&(las!=1||cpos==0))
     ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:21:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(z<pos[2].size()&&(las!=2||cpos==0))
     ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 699 ms 774436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 699 ms 774436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 774648 KB Output is correct
2 Correct 394 ms 774632 KB Output is correct
3 Correct 396 ms 774520 KB Output is correct
4 Correct 390 ms 774708 KB Output is correct
5 Correct 418 ms 774520 KB Output is correct
6 Correct 391 ms 774520 KB Output is correct
7 Correct 397 ms 774648 KB Output is correct
8 Correct 396 ms 774572 KB Output is correct
9 Correct 409 ms 774520 KB Output is correct
10 Correct 388 ms 774520 KB Output is correct
11 Correct 392 ms 774520 KB Output is correct
12 Correct 392 ms 774648 KB Output is correct
13 Correct 397 ms 774648 KB Output is correct
14 Correct 387 ms 774648 KB Output is correct
15 Correct 381 ms 774648 KB Output is correct
16 Correct 391 ms 774520 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 699 ms 774436 KB Time limit exceeded
2 Halted 0 ms 0 KB -