Submission #110135

#	Time	Username	Problem	Language	Result	Execution time	Memory
110135		Arturgo	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	1119 ms	151516 KiB

dango_maker

#include <iostream>
using namespace std;

string terrain[3000];

bool estPasse[3][3000][3000];
int dyn[3][3000][3000];

int nbLigs, nbCols;

bool estValide(int lig, int col) {
  return lig >= 0 && lig < nbLigs && col >= 0 && col < nbCols;
}

int maxLignes(int lig, int col, int peutBas) {
  if(lig <= -1 || col >= nbCols)
    return 0;
  
  if(estPasse[peutBas][lig][col])
    return dyn[peutBas][lig][col];
  estPasse[peutBas][lig][col] = true;

  bool valideBas = (peutBas == 0), valideDroite = true;

  if(terrain[lig][col] != 'R') {
    valideBas = false;
    valideDroite = false;
  }

  if(!estValide(lig + 1, col) || terrain[lig + 1][col] != 'G')
    valideBas = false;
  if(!estValide(lig + 2, col) || terrain[lig + 2][col] != 'W')
    valideBas = false;

  if(!estValide(lig, col + 1) || terrain[lig][col + 1] != 'G')
    valideDroite = false;
  if(!estValide(lig, col + 2) || terrain[lig][col + 2] != 'W')
    valideDroite = false;
  
  int maxi = maxLignes(lig - 1, col + 1, max(0, peutBas - 1)) + valideBas;

  if(valideDroite) {
    maxi = max(maxi, maxLignes(lig - 1, col + 1, 2) + 1);
  }
  
  dyn[peutBas][lig][col] = maxi;
  return maxi;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbLigs >> nbCols;

  for(int iLig = 0;iLig < nbLigs;iLig++) {
    cin >> terrain[iLig];
  }

  int totalLignes = 0;
  for(int iLig = 0;iLig < nbLigs;iLig++) {
    totalLignes += maxLignes(iLig, 0, 0);
  }

  for(int iCol = 1;iCol < nbCols;iCol++) {
    totalLignes += maxLignes(nbLigs - 1, iCol, 0);
  }

  cout << totalLignes << endl;
  return 0;
}

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