Assignment 03 Solution

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:

    1. About GPU memory M: The i_th GPU is installed on i_th day, of which the memory is of M_i units initially.

    2. 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).

    3. 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

    1. The first line includes a single integer N (1<=N<=10^5), the number of GPUs(days).

    2. 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.

    3. 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


    1. Consider using min/max heap / priority queue to find out which GPU is dead on each day.

    2. The wise computation of [prefix sum] may be useful to speed up your program.

    3. 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