E. Exciting Menus

Codeforces

IDCF10199E

Time4000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

In a restaurant, given N menus, where the menus are represented by the strings S1, ..., SN. Each string Si is associated with an array Ai (of the same length) of joy levels. In this problem, you should choose a submenu defined by three integers (i, j, k), where i is the index of one of the menus, and j, k specify a substring of this chosen menu. We need to find the submenu of the highest quality, where the quality Q is defined by the function: Can you find the submenu of the highest quality? Please output the corresponding highest quality of the function Q. The first line of the input contains a single integer T specifying the number of test cases. Each test case begins with a line containing an integer N (1 ≤ N ≤ 105) specifying the number of menus in the restaurant. Then N lines follow, the ith line contains a string Si representing the ith menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 105 per test case. Then N lines follow, the ith line contains array Ai, in which Ai has the same length as string Si and (0 ≤ Aik ≤ 109). The values of each array are space-separated. For each test case, print a single line containing an integer Q representing the maximum quality corresponding to the best submenu (i, j, k). The triples corresponding to the answers of the two given cases are (1, 1, 5) and (1, 4, 5). ## Input The first line of the input contains a single integer T specifying the number of test cases.Each test case begins with a line containing an integer N (1 ≤ N ≤ 105) specifying the number of menus in the restaurant.Then N lines follow, the ith line contains a string Si representing the ith menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 105 per test case.Then N lines follow, the ith line contains array Ai, in which Ai has the same length as string Si and (0 ≤ Aik ≤ 109). The values of each array are space-separated. ## Output For each test case, print a single line containing an integer Q representing the maximum quality corresponding to the best submenu (i, j, k). [samples] ## Note The triples corresponding to the answers of the two given cases are (1, 1, 5) and (1, 4, 5).

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ N_k, K_k \in \mathbb{Z} $ satisfy $ 1 \leq K_k \leq N_k \leq 200 $. **Constraints** 1. $ 1 \leq T \leq \text{unknown (but input-limited)} $ 2. For each test case: $ 1 \leq K_k \leq N_k \leq 200 $ **Objective** For each test case $ k $, compute the number of permutations $ \pi \in S_{N_k} $ such that the maximum length of a contiguous increasing subarray in $ \pi $ is exactly $ K_k $. Output the result modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "E. Exciting Menus",
    "description": {
      "content": "In a restaurant, given N menus, where the menus are represented by the strings S1, ..., SN. Each string Si is associated with an array Ai (of the same length) of joy levels. In this problem, you shoul",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10199E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a restaurant, given N menus, where the menus are represented by the strings S1, ..., SN. Each string Si is associated with an array Ai (of the same length) of joy levels. In this problem, you shoul...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ N_k, K_k \\in \\mathbb{Z} $ satisfy $ 1 \\leq K_k \\leq N_k \\leq 200 $.  \n\n**C...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments