oj.uz

Submission #884470

# Submission time Handle Problem Language Result Execution time Memory
884470 2023-12-07T12:43:00 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 262 ms 1017516 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()
const int INF=1e9;

int n;
vector<int> ind[3];
int dp[402][402][402][4];

int f(int a, int b, int c, char l){
	if(a+b+c==n) return 0;

	int &cur=dp[a][b][c][l];
	if(cur!=-1) return cur; 

	cur=INF;
	if(l==0){
		if(b!=ind[1].size()) cur=min(cur, f(a, b+1, c, 1)+max(0, ind[1][b]-(a+b+c)));
		if(c!=ind[2].size()) cur=min(cur, f(a, b, c+1, 2)+max(0, ind[2][c]-(a+b+c)));
	}
	else if(l==1){
		if(a!=ind[0].size()) cur=min(cur, f(a+1, b, c, 0)+max(0, ind[0][a]-(a+b+c)));
		if(c!=ind[2].size()) cur=min(cur, f(a, b, c+1, 2)+max(0, ind[2][c]-(a+b+c)));
	}
	else{
		if(b!=ind[1].size()) cur=min(cur, f(a, b+1, c, 1)+max(0, ind[1][b]-(a+b+c)));
		if(a!=ind[0].size()) cur=min(cur, f(a+1, b, c, 0)+max(0, ind[0][a]-(a+b+c)));
	}
	return cur;
}
int main(){
	string s;
	cin>>n>>s;

	memset(dp, -1, sizeof(dp));
	for(int i=0; i<n; i++){
		if(s[i]=='R')
			ind[0].push_back(i);
		else if(s[i]=='G')
			ind[1].push_back(i);
		else
			ind[2].push_back(i);
	}

	int ans=f(0, 0, 0, 3);
	cout<<(ans>=INF ? -1:ans)<<endl;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int f(int, int, int, char)':
joi2019_ho_t3.cpp:16:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |  int &cur=dp[a][b][c][l];
      |                       ^
joi2019_ho_t3.cpp:21:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if(b!=ind[1].size()) cur=min(cur, f(a, b+1, c, 1)+max(0, ind[1][b]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if(c!=ind[2].size()) cur=min(cur, f(a, b, c+1, 2)+max(0, ind[2][c]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if(a!=ind[0].size()) cur=min(cur, f(a+1, b, c, 0)+max(0, ind[0][a]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:26:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   if(c!=ind[2].size()) cur=min(cur, f(a, b, c+1, 2)+max(0, ind[2][c]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:29:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if(b!=ind[1].size()) cur=min(cur, f(a, b+1, c, 1)+max(0, ind[1][b]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:30:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(a!=ind[0].size()) cur=min(cur, f(a+1, b, c, 0)+max(0, ind[0][a]-(a+b+c)));
      |      ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 1017240 KB Output is correct
2 Correct 166 ms 1017368 KB Output is correct
3 Incorrect 169 ms 1017360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 1017240 KB Output is correct
2 Correct 166 ms 1017368 KB Output is correct
3 Incorrect 169 ms 1017360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1017432 KB Output is correct
2 Correct 168 ms 1017260 KB Output is correct
3 Correct 163 ms 1017452 KB Output is correct
4 Correct 167 ms 1017424 KB Output is correct
5 Correct 163 ms 1017356 KB Output is correct
6 Correct 166 ms 1017432 KB Output is correct
7 Correct 153 ms 1017516 KB Output is correct
8 Correct 157 ms 1017428 KB Output is correct
9 Correct 149 ms 1017428 KB Output is correct
10 Correct 154 ms 1017448 KB Output is correct
11 Correct 151 ms 1017424 KB Output is correct
12 Correct 148 ms 1017428 KB Output is correct
13 Correct 147 ms 1017404 KB Output is correct
14 Correct 149 ms 1017344 KB Output is correct
15 Correct 148 ms 1017284 KB Output is correct
16 Correct 144 ms 1017280 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 1017240 KB Output is correct
2 Correct 166 ms 1017368 KB Output is correct
3 Incorrect 169 ms 1017360 KB Output isn't correct
4 Halted 0 ms 0 KB -