제출 #375981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375981		peijar	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	345 ms	18284 KiB

dango_maker

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

const int MAXN = 3000;

char couleur[MAXN][MAXN];
int maxPossible[2*MAXN+1][2][2];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbLig, nbCol;
	cin >> nbLig >> nbCol;

	for (int iLig(0); iLig < nbLig; ++iLig)
		for (int iCol(0); iCol < nbCol; ++iCol)
			cin >> couleur[iLig][iCol];
	
	int rep(0);

	for (int iDiag(0); iDiag < nbLig + nbCol; ++iDiag)
	{
		// iLig + iCol = iDiag
		for (int i(0); i <= iDiag; ++i)
			for (int j(0); j < 2; ++j)
				for (int k(0); k < 2; ++k)
					maxPossible[i][j][k] = 0;
		int repAjout(0);
		for (int iCol(nbCol-1); iCol >= 0; --iCol)
		{
			int iLig = iDiag - iCol;
			if (iLig >= nbLig or iLig < 0)
				continue;
			bool djangoHoriz = false;
			if (iCol + 2 < nbCol and couleur[iLig][iCol] == 'R'
					and couleur[iLig][iCol+1] == 'G'
					and couleur[iLig][iCol+2] == 'W')
				djangoHoriz = true;
			bool djangoVerti = false;
			if (iLig + 2 < nbLig and couleur[iLig][iCol] == 'R'
					and couleur[iLig+1][iCol] == 'G'
					and couleur[iLig+2][iCol] == 'W')
				djangoVerti = true;
			maxPossible[iCol][0][0] = 
				max(djangoHoriz + maxPossible[iCol+1][0][0],
						maxPossible[iCol+1][0][1]);
			maxPossible[iCol][0][1] = 
				max(maxPossible[iCol+1][1][0], maxPossible[iCol+1][1][1]);
			for (int i(0); i < 2; ++i)
				for (int j(0); j < 2; ++j)
					maxPossible[iCol][1][i] = max(maxPossible[iCol][1][i],
							djangoVerti + maxPossible[iCol+1][i][j]);
			for (int i(0); i < 2; ++i)
				for (int j(0); j < 2; ++j)
					repAjout = max(repAjout, maxPossible[iCol][i][j]);
		}
		rep += repAjout;
	}
	cout << rep << endl;
}

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