codeforces-scrape

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

2063B.md (2378B)


      1 Source: https://codeforces.com/problemset/problem/2063/B
      2 
      3 B. Subsequence Update
      4 
      5 time limit per test
      6 
      7 1.5 seconds
      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 After Little John borrowed expansion screws from auntie a few hundred times, eventually she decided to come and take back the unused ones.
     22 
     23 But as they are a crucial part of home design, Little John decides to hide some in the most unreachable places — under the eco-friendly wood veneers.
     24 
     25  
     26 
     27 You are given an integer sequence $a_1, a_2, \ldots, a_n$, and a segment $[l,r]$ ($1 \le l \le r \le n$).
     28 
     29 You must perform the following operation on the sequence exactly once.
     30 
     31 * Choose any subsequence$^{\text{∗}}$ of the sequence $a$, and reverse it. Note that the subsequence does not have to be contiguous.
     32 
     33 Formally, choose any number of indices $i_1,i_2,\ldots,i_k$ such that $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$. Then, change the $i_x$-th element to the original value of the $i_{k-x+1}$-th element simultaneously for all $1 \le x \le k$.
     34 
     35 Find the minimum value of $a_l+a_{l+1}+\ldots+a_{r-1}+a_r$ after performing the operation.
     36 
     37 $^{\text{∗}}$A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) element from arbitrary positions.
     38 
     39 Input
     40 
     41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     42 
     43 The first line of each test case contains three integers $n$, $l$, $r$ ($1 \le l \le r \le n \le 10^5$) — the length of $a$, and the segment $[l,r]$.
     44 
     45 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_{i} \le 10^9$).
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     48 
     49 Output
     50 
     51 For each test case, output the minimum value of $a_l+a_{l+1}+\ldots+a_{r-1}+a_r$ on a separate line.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 6
     59 
     60 2 1 1
     61 
     62 2 1
     63 
     64 3 2 3
     65 
     66 1 2 3
     67 
     68 3 1 3
     69 
     70 3 1 2
     71 
     72 4 2 3
     73 
     74 1 2 2 2
     75 
     76 5 2 5
     77 
     78 3 3 2 3 5
     79 
     80 6 1 3
     81 
     82 3 6 6 4 3 2
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 1
     89 3
     90 6
     91 3
     92 11
     93 8
     94 ```
     95 
     96 Note
     97 
     98 On the second test case, the array is $a=[1,2,3]$ and the segment is $[2,3]$.
     99 
    100 After choosing the subsequence $a_1,a_3$ and reversing it, the sequence becomes $[3,2,1]$. Then, the sum $a_2+a_3$ becomes $3$. It can be shown that the minimum possible value of the sum is $3$.