Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Simple Distributed computing system
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 237Accepted: 87Special Judge


Since Jack did a fantastic job on the simple distributed storage system, his mentor pushes him into another project. One scenario of the project is that, given a set of machines and a set of Web applications with CPU demands, a placement controller should decide which server should be used for each application and how to deploy the instances of those applications.

We assume that there are n applications and m servers. Some instances for the applications are already set up on the servers. However, each server runs different set of instances, and their CPU capacity are also distinct. For instance, server A runs two instances for application X and Y, while server B runs two instances for application Y and Z. So server A can handle some requests for application X and Y, and server B can run some requests for application Y and Z. To simplify our problem, we assume that the CPU capacity and CPU requirement can be represented by integer.

A server is fully utilized if its residual CPU capacity is zero. An application instance is "fully utilized” if it runs on a fully utilized server, otherwise it is called "underutilized”. However, an instance can be "completely idle" if it has no load. A placement scheme is "efficient” as long as for each application, there is at most one instance of this application on the status of "underutilized” but not "completely idle".

Your task is to write a placement controller program to make an "efficient” assignment and maximize the total satisfied CPU demand of all the applications.

An application can be run on several instances, and those instances mutually satisfy the CPU requirement of that application. All the instances' CPU load on one server cannot exceed the CPU capacity of that server.


The first line of input file contains two integers n and m(n,m ≤ 200), representing the number of applications and the number of servers.

The second line contains n integers, representing the required CPU demand (≤ 1000)for each application. The application is numbered from 0 to n-1.

The following m lines describe the details of each server. In the ith line, the first integer represents CPU capacity of this server( ≤ 10000), and the second integer ki represents the number of instances running on it. Following is ki ( ≤ n)integers, ai,0, ai,1,…,ai,ki, representing the running instances for application ai,0, application ai,1,…, application ai,ki.


The first line of the output file is an integer representing the maximum satisfied demand.

The following m lines contain the details of your solution. The ith line contains ki integers, representing how many CPU load put on the instances running on ith server. The order should be exactly the same as the input file.

Sample Input

3 2
10 20 15
15 2 1 0
15 2 1 2

Sample Output

15 0
0 15


In the sample case, for the first server, instance for application 1 occupies the whole CPU (15 unit) and instance for application 0 is completed idle. For the second server, instance for application 2 is fully utilized while instance for application 1 is completed idle.


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator