Description
Motivation
The GPU resources of AI Cluster on SIST decide how efficiently students can implement their experiments. AI cluster can be seen as a collection of GPUs. Each day, deep-learning guys are hungry for newly-arrived GPU. More GPUs indicate more experiments, which makes their research work solid. To analyze the consumption of resources, the administrative stuff builds a mathematical model.
Statistic Details
Assumption
A simplified model is set up to simulate real-world scenario. Plus, for now, we only consider the memory of GPU as criterion, for several days:
Hardworking administrative stuff: A new GPU is installed at cluster every day.
Hungry students: To simplify the model, all GPU memory will be consumed by a constant every day. The demand for all accessible GPUs is the same every day, unless the consumption is larger than some GPU’s available memory(in thi s case, the consumption is equal to its rest of memory. Surplus is truncated).
Burst of consumption: However, the demand for GPU differs from day to day.
Extremely long programs: The occupied memory won’t be freed once it is occpied.
Introduce some notations to crystalize those assumptions:
-
About GPU memory M: The i_th GPU is installed on i_th day, of which the memory is of M_i units initially.
-
About memory consumption C: C_i units of memory will be consumed on i_th day for each accessible GPU(including the newly-installed GPU).
-
About how many days N: There are N GPUs in total (a.k.a: we consider N days).
Goal
Estimate the sum of memory consumption for each day(consider all GPUs, in units of memory).
Update: 11/14: Simplify the descriptions.
Update 11/15: Add hint for long data type.
Input
-
The first line includes a single integer N (1<=N<=10^5), the number of GPUs(days).
-
The second line includes N integers M_1, M_2, …, M_N (0<=M_i<=10^9), where M_i is the initial memory of a GPU installed on day i.
-
The third line includes N integers C_1, C_2, …, C_N (0<=C_i<=10^9), where C_i is the units of consumption for all GPUs on day i.
Output
A line of N integers, where the i_th integer represents the total consumption of all GPUs on day i.
-
Sample Input 1
Sample Output 1
3
5
14
13
20
10
5
5
7
5
Hint
-
Consider using min/max heap / priority queue to find out which GPU is dead on each day.
-
The wise computation of [prefix sum] may be useful to speed up your program.
-
Note that for saving memory and consumption, you may use the data type, long, or overflow may occur in some testcases.
In other words, assume d is the matrix of shortest path. the length of k-shortest path is the k-th element in the sorted array consisting of all d[i][j], where 1<=i<j<=n and n is the quantity of vertices.
Update 11/14 1:59: Fix the example of directed graph.
Input
-
The first line: three integers n,m,k (2<=n<=2*10^5, n – 1 <= m <= 2*10^5, 1<=k<=400), indicating n vertices, m edges and k-shortest
-
For next m lines: three integers x, y, w (1<=x, y <=n, 1<=w<=10^9, x!=y), indicating an edge between vertices x and y with weight w.
All inputs are legal. It is guaranteed that the given graph is connected, no self-loops and multiple edges.
Output
An integer, the length of k-th shortest path (path from vertex to itself not counted, paths from i to j and j to i are counted as one)
-
Sample Input 1
Sample Output 1
5107
61
1 2
35
1 3
43
4 5
79
5 3
61
5 2
97
2 4
54
1 4
52
1 5
38
3 2
86
3 4
11
Language: C++ Theme: Solarized Light
Problems
Announcements
Submissions
Rankings
View Contest
Information
|
ID |
302 |
|
Time Limit |
1000MS |
|
Memory Limit |
256MB |
|
IO Mode |
Standard IO |
|
Created By |
admin |
|
Level |
Mid |
|
Score |
100 |
|
Tags |
Show |
Statistic Details
You have solved the problem Submit
Fall 2019 | Online judge for CS101@ShanghaiTech
