Tiling Terrace (Problem J, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Ashar Fuadi

# Problem Statement

Talia has just bought an abandoned house in the outskirt of Jakarta. The house has a nice and long yard which can be represented as a one-dimensional grid containing $1 \times N$ cells. To beautify the house, Talia is going to build a terrace on the yard by tiling the cells. Each cell on the yard contains either soil (represented by the character ‘.’) or rock (represented by the character ‘#’), and there are at most 50 cells containing rocks.

Being a superstitious person, Talia wants to tile the terrace with mystical tiles that have the power to repel ghosts. There are three types of mystical tiles:

- **Type-1**: Covers $1 \times 1$ cell and can only be placed on a soil cell (“.”).
- **Type-2**: Covers $1 \times 2$ cells and can only be placed on two consecutive soil cells (“..”).
- **Type-3**: Covers $1 \times 3$ cells and can only be placed on consecutive soil-rock-soil cells (“.#.”).

Each tile of Type-1, Type-2, and Type-3 has the power to repel $G_1$, $G_2$, and $G_3$ ghosts per day, respectively.  
There are also some mystical rules which must be followed for the power to be effective:

- There should be no overlapping tiles, i.e. each cell is covered by at most one tile.
- There should be at most $K$ tiles of Type-1, while there are no limitations for tiles of Type-2 and Type-3.

Talia is scared of ghosts, thus, the terrace (which is tiled by mystical tiles) should be able to repel as many ghosts as possible. Help Talia to find the maximum number of ghosts that can be repelled per day by the terrace. Note that Talia **does not need** to tile all the cells on the yard as long as the number of ghosts that can be repelled by the terrace is maximum.

# Input

Input begins with a line containing five integers:  
$N\ K\ G_1\ G_2\ G_3$ ($1 \leq N \leq 100{,}000;\ 0 \leq K \leq N;\ 0 \leq G_1,G_2,G_3 \leq 1000$) representing the number of cells, the maximum number of tiles of Type-1, the number of ghosts repelled per day by a tile of Type-1, the number of ghosts repelled per day by a tile of Type-2, and the number of ghosts repelled by a tile of Type-3, respectively.  
The next line contains a string of $N$ characters representing the yard. Each character in the string is either ‘.’ which represents a soil cell or ‘#’ which represents a rock cell. There are at most 50 rock cells.

# Output

Output in a line an integer representing the maximum number of ghosts that can be repelled per day.

# Sample Input #1
```
6 4 10 25 40
..#...
```
# Sample Output #1
```
75
```
Explanation for the sample input/output #1

Let “A” be a tile of Type-1, “BB” be a tile of Type-2, and “CCC” be a tile of Type-3. The tiling “ACCCBB” in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$

# Sample Input #2
```
6 4 10 100 40
..#...
```
# Sample Output #2
```
210
```
Explanation for the sample input/output #2

This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling “BB#BBA” or “BB#ABB” produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$. Observe that the third cell is left untiled.

# Sample Input #3
```
7 2 30 10 100
..#...#
```
# Sample Output #3
160
```
Explanation for the sample input/output #3

The tiling “ACCCA.#”, “ACCC.#”, or “.CCCAA#” produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$. Observe that there is no way to tile the last cell.

Sample inputs:
6 4 10 25 40
..#...

6 4 10 100 40
..#...

7 2 30 10 100
..#...#

Sample outputs:
75

210

160

# Solution Analysis
Analysis author: Ashar Fuadi

The solution uses a combination of dynamic programming and greedy. Let $S$ be the number of characters ‘.’ (soils) in the input, and $R$ be the number of characters ‘#’ (rocks) in the input. Note that $R$ is at most $50$.

**Observation 1**  
Since type-3 tiles can only be placed on “.#.”, then the maximum possible number of type-3 tiles that can be placed is $R$ (which is at most $50$).

**Observation 2**  
Because we want to maximize the result, any placed type-2 tile can be replaced by two type-1 tiles (when $G_1 * 2 > G_2$), or one type-1 tile (when $G_1 > G_2$ and doing the former would exceed the limit of $K$).

The solution uses dynamic programming by assuming that we can only use type-2 and type-3 tiles. Type-1 tiles can then be inserted greedily using Observation 2.

Define $dp[i][j]$ be maximum number of type-2 tiles that can be used for tiling cells $[1..i]$, using exactly $j$ type-3 tiles. The recurrence is trivial: For each state, decide whether we want to leave the $i^{th}$ cell untiled, put type-2 tile, or put type-3 tile.

After we fill our DP table, we can brute-force $j$, the number of type-3 tiles used. For each $j$, we know that:

- The number of type-2 tiles used is $dp[N][j]$
- The number of type-3 tiles used is $j$
- The number of untiled soil cells is $S - 2 * dp[N][j] - 2 * j$
- We can put type-1 tiles on the untiled cells. Then, if we still have spare type-1 tiles left, we can greedily replace some of the type-2 tiles, using Observation 2.

The answer is the maximum result over all $j$. The time complexity is $O(NR)$.


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}