codeforces-scrape

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

1526C1.md (1497B)


      1 Source: https://codeforces.com/problemset/problem/1526/C1
      2 
      3 C1. Potions (Easy Version)
      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 This is the easy version of the problem. The only difference is that in this version $n \leq 2000$. You can make hacks only if both versions of the problem are solved.
     22 
     23 There are $n$ potions in a line, with potion $1$ on the far left and potion $n$ on the far right. Each potion increases your health by $a_i$ when drunk. $a_i$ can be negative, meaning that the potion decreases your health.
     24 
     25 You start with $0$ health, and you will walk from left to right, from the first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
     26 
     27 What is the largest number of potions you can drink?
     28 
     29 Input
     30 
     31 The first line contains a single integer $n$ ($1 \leq n \leq 2000$) — the number of potions.
     32 
     33 The next line contains $n$ integers $a_1$, $a_2$, ... ,$a_n$ ($-10^9 \leq a_i \leq 10^9$) which represent the change in health after drinking that potion.
     34 
     35 Output
     36 
     37 Output a single integer, the maximum number of potions you can drink without your health becoming negative.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 6
     45 
     46 4 -4 1 -3 1 -3
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 5
     53 ```
     54 
     55 Note
     56 
     57 For the sample, you can drink $5$ potions by taking potions $1$, $3$, $4$, $5$ and $6$. It is not possible to drink all $6$ potions because your health will go negative at some point