N. April Fools' Problem (medium)

Codeforces

IDCF802N

Time4000ms

Memory256MB

Difficulty—

binary searchflowsgraphs

English · Original

Chinese · Translation

Formal · Original

The marmots need to prepare _k_ problems for HC2 over _n_ days. Each problem, once prepared, also has to be printed. The preparation of a problem on day _i_ (at most one per day) costs _a__i_ CHF, and the printing of a problem on day _i_ (also at most one per day) costs _b__i_ CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine). What is the minimum cost of preparation and printing? ## Input The first line of input contains two space-separated integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 2200). The second line contains _n_ space-separated integers _a_1, ..., _a__n_ () — the preparation costs. The third line contains _n_ space-separated integers _b_1, ..., _b__n_ () — the printing costs. ## Output Output the minimum cost of preparation and printing _k_ problems — that is, the minimum possible sum _a__i_1 + _a__i_2 + ... + _a__i__k_ + _b__j_1 + _b__j_2 + ... + _b__j__k_, where 1 ≤ _i_1 < _i_2 < ... < _i__k_ ≤ _n_, 1 ≤ _j_1 < _j_2 < ... < _j__k_ ≤ _n_ and _i_1 ≤ _j_1, _i_2 ≤ _j_2, ..., _i__k_ ≤ _j__k_. [samples] ## Note In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

[{"iden":"statement","content":"旱獭需要在 #cf_span[n] 天内为 HC#cf_span[2] 准备 #cf_span[k] 道题目，每道题目准备完成后必须打印。\n\n在第 #cf_span[i] 天准备一道题目（每天最多准备一道）的费用为 #cf_span[ai] CHF，在第 #cf_span[i] 天打印一道题目（每天最多打印一道）的费用为 #cf_span[bi] CHF。当然，一道题目不能在被准备之前被打印（但在同一天完成准备和打印是允许的）。\n\n准备和打印的最小总费用是多少？\n\n输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（）——准备费用。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn]（）——打印费用。\n\n请输出准备和打印 #cf_span[k] 道题目的最小费用——即最小可能的和 #cf_span[ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk]，其中 #cf_span[1 ≤ i1 < i2 < ... < ik ≤ n]，#cf_span[1 ≤ j1 < j2 < ... < jk ≤ n]，且满足 #cf_span[i1 ≤ j1]，#cf_span[i2 ≤ j2]，...，#cf_span[ik ≤ jk]。\n\n在样例测试用例中，一种最优解是：在第 #cf_span[1] 天准备第一道题并在第 #cf_span[1] 天打印，第 #cf_span[2] 天准备第二道题并在第 #cf_span[4] 天打印，第 #cf_span[3] 天准备第三道题并在第 #cf_span[5] 天打印，第 #cf_span[6] 天准备第四道题并在第 #cf_span[8] 天打印。"}},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（）——准备费用。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn]（）——打印费用。"},{"iden":"output","content":"请输出准备和打印 #cf_span[k] 道题目的最小费用——即最小可能的和 #cf_span[ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk]，其中 #cf_span[1 ≤ i1 < i2 < ... < ik ≤ n]，#cf_span[1 ≤ j1 < j2 < ... < jk ≤ n]，且满足 #cf_span[i1 ≤ j1]，#cf_span[i2 ≤ j2]，...，#cf_span[ik ≤ jk]。"},{"iden":"note","content":"在样例测试用例中，一种最优解是：在第 #cf_span[1] 天准备第一道题并在第 #cf_span[1] 天打印，第 #cf_span[2] 天准备第二道题并在第 #cf_span[4] 天打印，第 #cf_span[3] 天准备第三道题并在第 #cf_span[5] 天打印，第 #cf_span[6] 天准备第四道题并在第 #cf_span[8] 天打印。"}]

Let $ n, k \in \mathbb{N} $ with $ 1 \leq k \leq n \leq 2200 $. Given two sequences $ a = (a_1, a_2, \dots, a_n) \in \mathbb{R}^n $ and $ b = (b_1, b_2, \dots, b_n) \in \mathbb{R}^n $, representing preparation and printing costs per day, respectively. We seek to choose two strictly increasing sequences of indices: - $ i_1 < i_2 < \dots < i_k $ (days of preparation), - $ j_1 < j_2 < \dots < j_k $ (days of printing), such that $ i_\ell \leq j_\ell $ for all $ \ell = 1, 2, \dots, k $, and minimize the total cost: $$ \sum_{\ell=1}^k a_{i_\ell} + \sum_{\ell=1}^k b_{j_\ell}. $$ **Objective:** Minimize $ \sum_{\ell=1}^k (a_{i_\ell} + b_{j_\ell}) $ subject to $ 1 \leq i_1 < i_2 < \dots < i_k \leq n $, $ 1 \leq j_1 < j_2 < \dots < j_k \leq n $, and $ i_\ell \leq j_\ell $ for all $ \ell \in \{1, \dots, k\} $.

Samples

Input #1

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "N. April Fools' Problem (medium)",
    "description": {
      "content": "The marmots need to prepare _k_ problems for HC2 over _n_ days. Each problem, once prepared, also has to be printed. The preparation of a problem on day _i_ (at most one per day) costs _a__i_ CHF, an",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802N"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The marmots need to prepare _k_ problems for HC2 over _n_ days. Each problem, once prepared, also has to be printed.\n\nThe preparation of a problem on day _i_ (at most one per day) costs _a__i_ CHF, an...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"旱獭需要在 #cf_span[n] 天内为 HC#cf_span[2] 准备 #cf_span[k] 道题目，每道题目准备完成后必须打印。\\n\\n在第 #cf_span[i] 天准备一道题目（每天最多准备一道）的费用为 #cf_span[ai] CHF，在第 #cf_span[i] 天打印一道题目（每天最多打印一道）的费用为 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n, k \\in \\mathbb{N} $ with $ 1 \\leq k \\leq n \\leq 2200 $.  \nGiven two sequences $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{R}^n $ and $ b = (b_1, b_2, \\dots, b_n) \\in \\mathbb{R}^n $, representing ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments