codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2167G.md (2053B)


      1 Source: https://codeforces.com/problemset/problem/2167/G
      2 
      3 G. Mukhammadali and the Smooth Array
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Muhammadali has an integer array $a_1,\dots,a_n$. He can change (replace) any subset of positions; changing position $i$ costs $c_i$ and replaces $a_i$ with any integer of his choice. The positions that he does not change must retain their original values.
     22 
     23 After all changes, we call an index $i$ ($1 \le i \lt n$) a drop if the final value at position $i$ is strictly greater than the final value at position $i+1$. Muhammadali wants the final array to contain no drops.
     24 
     25 Find the minimum cost of changes required to ensure that there are no drops in the array.
     26 
     27 Input
     28 
     29 The first line contains an integer $t$ ($1 \le t \le 5000$) — the number of test cases.
     30 
     31 Each test case consists of three lines:
     32 
     33 The first line contains a single integer $n$ ($1 \le n \le 8000$) — the length of the arrays.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.
     36 
     37 The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of changes.
     38 
     39 It is guaranteed that the sum of $n$ across all test cases does not exceed $8000$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the minimum possible total cost required to eliminate all drops.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 10
     51 
     52 1
     53 
     54 10
     55 
     56 5
     57 
     58 4
     59 
     60 1 2 2 3
     61 
     62 5 6 7 8
     63 
     64 4
     65 
     66 4 3 2 1
     67 
     68 1 1 1 1
     69 
     70 3
     71 
     72 3 1 2
     73 
     74 100 1 1
     75 
     76 5
     77 
     78 5 5 5 5 5
     79 
     80 10 1 10 1 10
     81 
     82 5
     83 
     84 1 3 2 2 4
     85 
     86 100 1 1 1 100
     87 
     88 6
     89 
     90 10 9 8 7 6 5
     91 
     92 1 100 1 100 1 100
     93 
     94 5
     95 
     96 100 1 100 100 100
     97 
     98 1 100 1 1 1
     99 
    100 4
    101 
    102 2 1 2 1
    103 
    104 5 4 3 2
    105 
    106 7
    107 
    108 1 5 3 4 2 6 7
    109 
    110 10 1 10 1 10 1 10
    111 ```
    112 
    113 Output
    114 
    115 ```
    116 0
    117 
    118 0
    119 
    120 3
    121 
    122 2
    123 
    124 0
    125 
    126 1
    127 
    128 203
    129 
    130 1
    131 
    132 6
    133 
    134 11
    135 ```
    136 
    137 Note
    138 
    139 In the first and second examples, the array already has no drops, so no changes are needed.
    140 
    141 In the third example, one of the optimal arrays is: $[2,3,5,6]$; to achieve this, all elements except the second need to be replaced, so the answer is $c_1 + c_3 + c_4 = 3$.