report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Cow exhibition - FlandreOJ: Flandre Online Judge

Cow exhibition

Time limit: 1000 ms
Memory limit: 256 MB
Given $n$ cows, each cow $i$ has an IQ of $a_i$ and an EQ of $b_i$. You want to select some cows (you may select none) such that the sum of their total IQ and EQ is maximized, while the individual sums of IQ and EQ are both non-negative. ### Input - The first line contains an integer $n$. - The next $n$ lines each contain two integers $a_i$ and $b_i$. ### Output - Print a single integer which is the maximum possible sum of the total IQ and EQ of the selected cows. ### Constraints - $1 \le n \le 500$. - $|a_i|, |b_i| \le 1000$. ### Example Input: ``` 5 -5 7 8 -6 6 -3 2 1 -8 -5 ``` Output: ``` 8 ``` Explanation: - Select cows $1$, $3$, and $4$. - Including cow $2$ would result in a total of $10$, but the total EQ would be negative.
Introduction to Dynamic Programming (Part two)
Sake game
Coins
Coins 2
Game on array
Longest increasing subsequence 2
Convolution
Regular bracket sequence
Faulty addition
Weird bank
Delete operation
Palindromize
Color ribbon
Unique subsequences
Unique subsequences 2
Cow exhibition
Knapsack 3
Compressing array
Regular bracket sequence 2
Maximum path 3
Concating substring
Soil
Stacking boxes
String transformation
Palindromic quadruple
Finding teammates
Topic
Dynamic Programming
Rating 1500
Source USACO
Solution (1) Solution