F. Anti-Palindromize

Codeforces

IDCF884F

Time2000ms

Memory256MB

Difficulty—

flowsgraphsgreedy

English · Original

Chinese · Translation

Formal · Original

A string _a_ of length _m_ is called _antipalindromic_ iff _m_ is even, and for each _i_ (1 ≤ _i_ ≤ _m_) _a__i_ ≠ _a__m_ - _i_ + 1. Ivan has a string _s_ consisting of _n_ lowercase Latin letters; _n_ is even. He wants to form some string _t_ that will be an _antipalindromic_ permutation of _s_. Also Ivan has denoted the _beauty_ of index _i_ as _b__i_, and the _beauty_ of _t_ as the sum of _b__i_ among all indices _i_ such that _s__i_ = _t__i_. Help Ivan to determine maximum possible _beauty_ of _t_ he can get. ## Input The first line contains one integer _n_ (2 ≤ _n_ ≤ 100, _n_ is even) — the number of characters in _s_. The second line contains the string _s_ itself. It consists of only lowercase Latin letters, and it is guaranteed that its letters can be reordered to form an _antipalindromic_ string. The third line contains _n_ integer numbers _b_1, _b_2, ..., _b__n_ (1 ≤ _b__i_ ≤ 100), where _b__i_ is the _beauty_ of index _i_. ## Output Print one number — the maximum possible _beauty_ of _t_. [samples]

长度为 #cf_span[m] 的字符串 #cf_span[a] 被称为 _antipalindromic_，当且仅当 #cf_span[m] 为偶数，且对每个 #cf_span[i]（#cf_span[1 ≤ i ≤ m]）都有 #cf_span[ai ≠ am - i + 1]。 Ivan 有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]；#cf_span[n] 为偶数。他希望构造一个字符串 #cf_span[t]，它是 #cf_span[s] 的一个 _antipalindromic_ 排列。此外，Ivan 将索引 #cf_span[i] 的 _beauty_ 定义为 #cf_span[bi]，而字符串 #cf_span[t] 的 _beauty_ 定义为所有满足 #cf_span[si = ti] 的索引 #cf_span[i] 对应的 #cf_span[bi] 之和。请帮助 Ivan 确定他能得到的最大可能 _beauty_。第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]，#cf_span[n] 为偶数）——字符串 #cf_span[s] 中的字符数。第二行包含字符串 #cf_span[s] 本身。它仅由小写拉丁字母组成，且保证其字母可以重新排列成一个 _antipalindromic_ 字符串。第三行包含 #cf_span[n] 个整数 #cf_span[b1], #cf_span[b2], ..., #cf_span[bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 是索引 #cf_span[i] 的 _beauty_。输出一个数字——#cf_span[t] 可能的最大 _beauty_。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]，#cf_span[n] 为偶数）——字符串 #cf_span[s] 中的字符数。第二行包含字符串 #cf_span[s] 本身。它仅由小写拉丁字母组成，且保证其字母可以重新排列成一个 _antipalindromic_ 字符串。第三行包含 #cf_span[n] 个整数 #cf_span[b1], #cf_span[b2], ..., #cf_span[bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 是索引 #cf_span[i] 的 _beauty_。 ## Output 输出一个数字——#cf_span[t] 可能的最大 _beauty_。 [samples]

Let $ n $ be an even positive integer, $ s \in \Sigma^n $ a string over lowercase Latin letters, and $ b \in \mathbb{Z}^n $ a vector of beauties. Define a permutation $ t $ of $ s $ to be **antipalindromic** if: - $ t_i \ne t_{n-i+1} $ for all $ i \in \{1, 2, \dots, n\} $. Define the **beauty** of $ t $ as: $$ \sum_{i=1}^n b_i \cdot \mathbf{1}_{s_i = t_i} $$ **Objective:** Maximize the beauty over all antipalindromic permutations $ t $ of $ s $, given that at least one such permutation exists. --- **Formal Statement:** Given: - $ n \in 2\mathbb{N} $, $ 2 \le n \le 100 $ - $ s \in \Sigma^n $, $ \Sigma = \{a, b, \dots, z\} $ - $ b \in \mathbb{Z}^n $, $ 1 \le b_i \le 100 $ - $ s $ is such that at least one antipalindromic permutation exists Find: $$ \max_{t \in \text{Perm}(s),\; t \text{ antipalindromic}} \sum_{i=1}^n b_i \cdot [s_i = t_i] $$ Where $ \text{Perm}(s) $ denotes the set of all strings that are permutations of $ s $, and $ t $ is antipalindromic iff $ \forall i \in [1, n],\; t_i \ne t_{n-i+1} $.

Samples

Input #1

8
abacabac
1 1 1 1 1 1 1 1

Output #1

Input #2

8
abaccaba
1 2 3 4 5 6 7 8

Output #2

Input #3

8
abacabca
1 2 3 4 4 3 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Anti-Palindromize",
    "description": {
      "content": "A string _a_ of length _m_ is called _antipalindromic_ iff _m_ is even, and for each _i_ (1 ≤ _i_ ≤ _m_) _a__i_ ≠ _a__m_ - _i_ + 1. Ivan has a string _s_ consisting of _n_ lowercase Latin letters; _n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF884F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string _a_ of length _m_ is called _antipalindromic_ iff _m_ is even, and for each _i_ (1 ≤ _i_ ≤ _m_) _a__i_ ≠ _a__m_ - _i_ + 1.\n\nIvan has a string _s_ consisting of _n_ lowercase Latin letters; _n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "长度为 #cf_span[m] 的字符串 #cf_span[a] 被称为 _antipalindromic_，当且仅当 #cf_span[m] 为偶数，且对每个 #cf_span[i]（#cf_span[1 ≤ i ≤ m]）都有 #cf_span[ai ≠ am - i + 1]。\n\nIvan 有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]；#cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n $ be an even positive integer, $ s \\in \\Sigma^n $ a string over lowercase Latin letters, and $ b \\in \\mathbb{Z}^n $ a vector of beauties.\n\nDefine a permutation $ t $ of $ s $ to be **antipalin...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments