Submission #723517

#	Time	Username	Problem	Language	Result	Execution time	Memory
723517		pcc	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	35 ms	8020 KiB

joi2019_ho_t3

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

#define debug(x) cout<<#x<<':'<<x<<endl;
#define int long long
const int mxn = 404;
const int inf = mxn*mxn*mxn;
int dp[2][mxn][mxn][3];
string s;
vector<int> pos[3];
int pref[mxn][3];

int calc(int sx,int sy,int sz,int ex,int ey,int ez){
	return max(ex-sx,0LL)+max(ey-sy,0LL)+max(ez-sz,0LL);
}

main(){
	int n;
	cin>>n>>s;
	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);
	}
	for(int i = 0;i<n;i++){
		if(i != 0)for(int j = 0;j<3;j++)pref[i][j] = pref[i-1][j];
		if(s[i] == 'R')pref[i][0]++;
		else if(s[i] == 'G')pref[i][1]++;
		else pref[i][2]++;
	}
	//for(int i = 0;i<n;i++)cout<<pref[i][0]<<' '<<pref[i][1]<<' '<<pref[i][2]<<endl;
	bool roll = 0;
	for(auto &i:dp)for(auto &j:i)for(auto &k:j)for(auto &kk:k)kk = inf;
	if(pos[0].size()>0)dp[roll][1][0][0] = pos[0][0];
	if(pos[1].size()>0)dp[roll][0][1][1] = pos[1][0];
	if(pos[2].size()>0)dp[roll][0][0][2] = pos[2][0];
	//for(int i = 0;i<3;i++){cout<<i<<":";for(auto &j:pos[i])cout<<j<<' ';cout<<endl;}
	for(int i = 1;i<n;i++){
		roll^=1;
		for(int j = 0;j<=pos[0].size();j++){
			for(int k = 0;k<=pos[1].size();k++){
				int l = i+1-j-k;
				fill(dp[roll][j][k],dp[roll][j][k]+3,inf);
				if(l<0||l>pos[2].size())continue;

				if(j>0)dp[roll][j][k][0] = min(dp[roll^1][j-1][k][1],dp[roll^1][j-1][k][2])+
					calc(j,k,l,pref[pos[0][j-1]][0],pref[pos[0][j-1]][1],pref[pos[0][j-1]][2]);

				if(k>0)dp[roll][j][k][1] = min(dp[roll^1][j][k-1][0],dp[roll^1][j][k-1][2])+
					calc(j,k,l,pref[pos[1][k-1]][0],pref[pos[1][k-1]][1],pref[pos[1][k-1]][2]);

				if(l>0)dp[roll][j][k][2] = min(dp[roll^1][j][k][1],dp[roll^1][j][k][0])+
					calc(j,k,l,pref[pos[2][l-1]][0],pref[pos[2][l-1]][1],pref[pos[2][l-1]][2]);

				//cout<<i<<' '<<j<<' '<<k<<' '<<l<<":";for(auto &kk:dp[roll][j][k])cout<<kk<<' ';cout<<'\n';
			}
		}
	}
	for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
	int ans = *min_element(dp[roll][pos[0].size()][pos[1].size()],dp[roll][pos[0].size()][pos[1].size()]+3);
	if(ans>=inf)cout<<-1;
	else cout<<ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main(){
      | ^~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j = 0;j<=pos[0].size();j++){
      |                 ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int k = 0;k<=pos[1].size();k++){
      |                  ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if(l<0||l>pos[2].size())continue;
      |             ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
      |                ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:59:51: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
      |                                                  ~^~~~~~~~~~~~~~

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