Personnel Allocation (APCS 2020-10 Beginner)

Points 100 1.0s 256M

A company has \(n\) employees and two factories. If factory 1 and factory 2 receive \(X_1\) and \(X_2\) employees respectively, their revenues \(Y_1\) and \(Y_2\) are

\[Y_1 = A_1 X_1^2 + B_1 X_1 + C_1\] \[Y_2 = A_2 X_2^2 + B_2 X_2 + C_2\]

Consider all ways of allocating the employees and output the maximum total revenue. Note that every employee must be allocated to one of the factories (so \(X_1 + X_2 = n\) with \(X_1, X_2 \ge 0\); one factory may receive \(0\) employees).

Input

The first line contains three integers \(A_1\), \(B_1\), \(C_1\).

The second line contains three integers \(A_2\), \(B_2\), \(C_2\).

The third line contains a positive integer \(n\).

Constraints

  • \(1 \le n \le 100\)
  • \(-1000 \le A_1, B_1, C_1, A_2, B_2, C_2 \le 1000\)

Output

Output the maximum total revenue (which may be negative).

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

  • Subtask 1 (\(50\) points): \(n = 2\).
  • Subtask 2 (\(50\) points): \(1 \le n \le 100\).

Sample Input

2 -1 3
4 -5 2
2

Sample Output

11

Sample Explanation

\(n = 2\). With \(X_1 = 0, X_2 = 2\): \(Y_1 = 3\), \(Y_2 = 4 \cdot 4 - 5 \cdot 2 + 2 = 8\), total \(11\). With \(X_1 = 2, X_2 = 0\): \(Y_1 = 2 \cdot 4 - 2 + 3 = 9\), \(Y_2 = 2\), total \(11\). The maximum is \(11\).

Source

APCS programming exam, October 2020, Problem 1.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.