P5813 [WC2001] High-Performance Computer

You now have a time-critical engineering computation task to complete, as the chief engineer of a national high-performance parallel computer. To make full use of the advantages of parallel computing, the computation task should be split into several smaller subtasks. This large computation task consists of two independent smaller computation tasks, $A$ and $B$. To fully use the computing power of the parallel computer, these tasks need to be decomposed. It is found that both $A$ and $B$ can each be divided into many smaller subtasks. The workload of all type $A$ subtasks is the same, and the workload of all type $B$ subtasks is also the same (the workloads of type $A$ and type $B$ subtasks are not necessarily the same). There is no required execution order between tasks $A$ and $B$, nor among the subtasks. This supercomputer has $p$ computing nodes. Each node includes a serial processor, local main memory, and high-speed cache. However, due to long-term use and inconsistent upgrades, the computing abilities of the nodes are not symmetric. A node’s computing ability includes the following aspects: 1. For this task, each node has three working states: standby, type $A$, and type $B$. In type $A$ state it executes type $A$ tasks; in type $B$ state it executes type $B$ tasks; in standby state it does not compute. All processors are in standby before starting work. Switching from any other state into working state $A$ or $B$ (including switching between $A$ and $B$) requires a certain startup time. This time may differ across nodes. Use two positive integers $t_{i}^{A}$ and $t_{i}^{B}$ ($i = 1,2,\cdots,p$) to represent the startup time (in ns) for node $i$ to enter working state $A$ and working state $B$, respectively. 2. When a node continuously processes tasks of the same type, the execution time (excluding state switching time) grows with the square of the task amount (the number of subtasks of that type), i.e.: If node $i$ continuously processes $x$ type $A$ subtasks, the corresponding execution time is $t = k_{i}^{A} x^2$. Similarly, if node $i$ continuously processes $x$ type $B$ subtasks, the corresponding execution time is $t = k_{i}^{B} x^2$. Here, $k_{i}^{A}$ and $k_{i}^{B}$ are coefficients in ns, for $i = 1,2,\cdots,p$. Task assignment must be completed before any computation starts. “Task assignment” means setting a task queue for each computing node. The queue consists of a sequence of type $A$ and type $B$ subtasks. The two types of subtasks can be interleaved. After computation starts, each node reads computation tasks from its own task queue in order and executes them. A consecutive block of same-type subtasks in the queue will be read and executed by that node in one batch, and such a consecutive block cannot be split into two parts for execution. You need to write a program to schedule the computation tasks for these $p$ nodes so that the engineering computation task can be completed as early as possible. Assume the schedule will not change after being set, and all nodes start running at the same time. The goal is to make the completion time of the last finishing node as early as possible.

The first line describes the computation tasks, containing two positive integers $n_A$ and $n_B$, which are the numbers of type $A$ and type $B$ subtasks, respectively. The two integers are separated by one space. The following part describes the computer: The second line contains an integer $p$, the number of computing nodes. Then follow $p$ lines describing the nodes in order. Node $i$ is described on line $i+2$, which contains four positive integers (separated by one space): $t_{i}^{A},t_{i}^{B},k_{i}^{A},k_{i}^{B}$.

Only one line containing one positive integer: the time from when all nodes start computing until the task is completed.

For all testdata: $1 \le n_A \le 60$, $1 \le n_B \le 60$, $1 \le p \le 20$, $1 \le t_{i}^{A} \le 1000$, $1 \le t_{i}^{B} \le 1000$, $1 \le k_{i}^{A} \le 50$, $1 \le k_{i}^{B} \le 50$。 Translated by ChatGPT 5