Submission #330458

#	Time	Username	Problem	Language	Result	Execution time	Memory
330458		GioChkhaidze	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	80 ms	3052 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

const int N=404;

char c;
int n,Cr,Cg,Cy,t,id,A,B,x,y;
int a[N];
int dp[N][N][4],dp_[N][N][4];
int R[N],G[N],Y[N];

vector < int > v[4];

main () {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>c;
		R[i]=R[i-1]+(c=='R');
		G[i]=G[i-1]+(c=='G');
		Y[i]=Y[i-1]+(c=='Y');
		
		if (c=='R') a[i]=0;	
			else
		if (c=='G') a[i]=1;
			else
		if (c=='Y') a[i]=2;
	
		v[a[i]].push_back(i);
	}
	
	for (Cr=0; Cr<=v[0].size(); Cr++)
		for (Cg=0; Cg<=v[1].size(); Cg++)
			for (t=0; t<3; t++) 
				dp_[Cr][Cg][t]=1e9;

	dp_[0][0][0]=0;
	dp_[0][0][1]=0;
	dp_[0][0][2]=0;
	
	for (int i=1; i<=n; i++) {
		
		for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
			for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++)
				for (t=0; t<3; t++) {
					dp[Cr][Cg][t]=1e9;
				}
		
		for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
			for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++) {
				Cy=i-Cr-Cg;
				if (Cy>v[2].size()) continue;
				
				if (Cr) {
					id=v[0][Cr-1];
					A=max(0,Cg-G[id]),B=max(0,Cy-Y[id]);
					dp[Cr][Cg][0]= min(dp_[Cr-1][Cg][1],dp_[Cr-1][Cg][2]) + A + B;
				}
				
				if (Cg) {
					id=v[1][Cg-1];
					A=max(0,Cr-R[id]),B=max(0,Cy-Y[id]);
					dp[Cr][Cg][1]= min(dp_[Cr][Cg-1][0],dp_[Cr][Cg-1][2]) + A + B;
				}	
				
				if (Cy) {
					id=v[2][Cy-1];
					A=max(0,Cr-R[id]),B=max(0,Cg-G[id]);
					dp[Cr][Cg][2]= min(dp_[Cr][Cg][0],dp_[Cr][Cg][1]) + A + B;
				}				
			}
			
		for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
			for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++)
				for (t=0; t<=2; t++) 
					dp_[Cr][Cg][t]=dp[Cr][Cg][t];
	}
	
	int ans=1e9;
	for (t=0; t<3; ++t) {
		ans=min(ans,dp_[v[0].size()][v[1].size()][t]);
	}
	
	if (ans==1e9) ans=-1;
	cout<<ans<<"\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp:14:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main () {
      |       ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (Cr=0; Cr<=v[0].size(); Cr++)
      |             ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (Cg=0; Cg<=v[1].size(); Cg++)
      |              ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
      |                       ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++)
      |                           ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
      |                       ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:49:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++) {
      |                           ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:51:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if (Cy>v[2].size()) continue;
      |         ~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:72:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (Cr=0; Cr<=i && Cr<=v[0].size(); Cr++)
      |                       ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:73:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for (Cg=0; Cg+Cr<=i && Cg<=v[1].size(); Cg++)
      |                           ~~^~~~~~~~~~~~~

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