problem.txt (2861B)
1 C. Remove the Ends 2 Finished 3 Practice 4 time limit per test: 3 seconds 5 memory limit per test: 256 megabytes 6 You have an array a of length n consisting of non-zero integers. Initially, you have 0 coins, 7 and you will do the following until a is empty: 8 • Let m be the current size of a. Select an integer i where 1 ≤ i ≤ m , gain |ai | ∗ coins, 9 and then: 10 ◦ if ai < 0, then replace a with [a1 , a2 , … , ai−1 ] (that is, delete the suffix beginning 11 with ai ); 12 ◦ otherwise, replace a with [ai+1 , ai+2 , … , am ] (that is, delete the prefix ending with 13 ai ). 14 → Virtual participation 15 Virtual contest is a way to take part in past contest, 16 as close as possible to participation on time. It is 17 supported only ICPC mode for virtual contests. If 18 you've seen these problems, a virtual contest is not 19 for you - solve these problems in the archive. If you 20 just want to solve some problem from a contest, a 21 virtual contest is not for you - solve this problem in 22 the archive. Never use someone else's code, read 23 the tutorials or communicate with other person 24 during a virtual contest. 25 Find the maximum number of coins you can have at the end of the process. 26 ∗ 27 28 Start virtual contest 29 Here |ai | represents the absolute value of ai : it equals ai when ai > 0 and −ai when ai < 0 . 30 31 --- 32 33 - array a of size n 34 - all non-zeros 35 - start with 0 coins 36 - do while size != n: 37 - select an element of a and add |a_i| coins 38 - one indexed, from 1 -> m (where m is remaining coins) 39 - if a_i < 0 then delete the suffix beginning with a_i 40 - else delete the prefix beginning with a_i 41 - compute max coins possible 42 --- 43 44 thoughts: 45 46 we see that state at a given point in time is a triple: 47 - (left, right, coins) 48 - where left is the leftmost element that hasn't been dropped 49 - where right is the rightmost element that hasn't been dropped 50 - we can do this because the left and right are removed in order 51 52 seems easily dp, but could also be a simple greedy approach that might be cheaper 53 54 --- 55 56 while the leftmost element is >= 0, we should always take it 57 while the rightmost element is < 0, we should always take it 58 59 60 --- 61 62 6 63 3 1 4 -1 -5 -9 64 65 take 3,1, and 4 66 67 -1 -5 -9 68 69 take -9,-5,-1 70 71 we get 8 + 15 = 23 72 73 --- 74 75 6 76 -10 -3 -17 1 19 20 77 78 79 in the bad cases, we are most interested in the righmost negative, and the leftmost positive. 80 81 we could do either: 1, 19, 20 82 or: -17,-3,-10 83 84 vs 30 85 vs 40 86 87 so we take the 40 88 89 --- 90 91 1 92 1 93 94 --- 95 96 these examples are kinda trash because they don't have complex combinations, or is this just a general problem? 97 98 like we first check leftmost, rightmost, then left run, right run? 99 100 what about inner options 101 102 --- 103 104 maybe we just do a naive dp approach because it seems in any case we'll have to do some amount of backtracking. 105 106 this approach is as follows: 107 108 - compute best from given state where: 109 - state := (left,right)