DMPG '15 G5 - ExpedColle

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are playing a popular browser game where you collect fleet girls to fight against enemies, the Abyssals. However, you prefer to spend your time playing ExpedColle, a "sub-game" where all you do is run expeditions all day, getting the most resources out of your time. There are many different classifications of ships in the game, but the only one relevant to you is the Mutsuki-class destroyer. The Mutsuki-class is famous for its low resource costs while on expedition.

An expedition is an action you can perform that starts a timer. When the timer completes, you gain a certain amount of resources (fuel, ammo, steel, or bauxite) and/or other items. And after completing an expedition, you must resupply your ships, which uses up some resources (typically fuel and ammo). In the game, there are many different expeditions. Expeditions can be organized by the world they take place in. In total, there are N worlds in the game. Each world can be described with nine parameters, E, C_1, V_1, CA, CB, CM, VA, VB, and VM. E is the number of expeditions available to you in that world. To simplify our model a little bit, we can say that the resource cost of an expedition is C_i and the revenue from completing it is V_i. For each world, the first expedition has cost C_1 and revenue V_1. Every subsequent expedition i has cost C_i = (C_{i-1} \times CA + CB) \bmod CM and value V_i = (V_{i-1} \times VA + VB) \bmod VM.

You want to seem like an elite player, so you refuse to do any expedition more than once. You have R resources to spend in total on performing expeditions. What is the maximum revenue you can make? You do not necessarily have to spend all of your resources. Note that completing expeditions does not give you more usable resources to initiate other expeditions.

Input Specification

The first line of input will have N and R.
The next N lines of input will each have E, C_1, V_1, CA, CB, CM, VA, VB, VM (one line per world).


For all subtasks,
1 \le N \le 2\,000
1 \le R \le 2\,000
0 \le C_1, CA, CB < CM \le 10^9
0 \le V_1, VA, VB < VM \le 10^9

Subtask 1 [40%]

The sum of E over all worlds does not exceed 10^5.

Subtask 2 [60%]

The sum of E over all worlds does not exceed 10^7.

Output Specification

Output the maximum revenue within the given resource budget.

Sample Input

2 25
1 10 10 99 99 100 99 99 100
5 3 2 4 7 11 6 7 13

Sample Output


Explanation of Output for Sample Input

The expeditions in (cost, value) pairs are:

  • World 1: (10, 10)
  • World 2: (3, 2), (8, 6), (6, 4), (9, 5), (10, 11)

Do the first expedition from world 1, the first expedition from world 2, and the last expedition from world 2 for a total cost of 10 + 3 + 10 = 23 and value of 10 + 2 + 11 = 23.


There are no comments at the moment.