Submission #949817

#	Time	Username	Problem	Language	Result	Execution time	Memory
949817		amirhoseinfar1385	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	430 ms	208644 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
const int maxn=3005;
int all[maxn][maxn],n,m,mainres=0,row[maxn][maxn],cal[maxn][maxn];
vector<pair<int,int>>asabnadaram[maxn*2];
struct fdp{
	int r,c;
	fdp(){
		r=c=0;
	}
};

void vorod(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='R'){
				all[i][j]=1;
			}else if(c=='G'){
				all[i][j]=2;
			}else{
				all[i][j]=3;
			}
			//cin>>all[i][j];
		}
	}
}

void pre(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(all[i][j]==1&&all[i][j+1]==2&&all[i][j+2]==3){
				row[i][j]=1;
			}
			if(all[i][j]==1&&all[i+1][j]==2&&all[i+2][j]==3){
				cal[i][j]=1;
			}
		}
	}
}


void calres(vector<pair<int,int>>v){
	vector<fdp>dp(v.size());
	for(int i=4;i<v.size();i++){
		if(v[i].first==0){
			dp[i].r=max(dp[i-1].r,dp[i-1].c);
		}else{
			dp[i].r=max(dp[i-1].r,dp[i-1].c)+1;
		}
		dp[i].c=max(dp[i-1].c,max(dp[i-2].c,max(dp[i-3].r,dp[i-3].c)));
		if(v[i].second){
			dp[i].c++;
		}
	//	cout<<"wtf: "<<i<<" "<<dp[i].r<<" "<<dp[i].c<<"\n";
	}
	mainres+=max(dp.back().c,dp.back().r);
}

void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
		//	cout<<i<<" "<<j<<" "<<row[i][j]<<" "<<cal[i][j]<<endl;
			asabnadaram[i+j].push_back(make_pair(row[i][j],cal[i][j]));
		}
	}
	for(int i=0;i<maxn*2;i++){
		asabnadaram[i].push_back(make_pair(0,0));
		asabnadaram[i].push_back(make_pair(0,0));
		asabnadaram[i].push_back(make_pair(0,0));
		asabnadaram[i].push_back(make_pair(0,0));
		reverse(asabnadaram[i].begin(),asabnadaram[i].end());
	}
	for(int i=0;i<maxn*2;i++){
		calres(asabnadaram[i]);
	//	if((int)asabnadaram[i].size()>4){
	//		cout<<i<<" "<<mainres<<"\n";
	//	}
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

Compilation message (stderr)

dango_maker.cpp: In function 'void calres(std::vector<std::pair<int, int> >)':
dango_maker.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=4;i<v.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67