Training - Passeggiata impegnativa

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

Scarica la traccia in C: passeggiata.c

Scarica la traccia in C++: passeggiata.cpp

Scarica la traccia in C#: passeggiata.cs

Scarica la traccia in Go: passeggiata.go

Scarica la traccia in JavaScript (HTML): passeggiata.html

Scarica la traccia in Java: passeggiata.java

Scarica la traccia in JavaScript (wasm-ide): passeggiata.js

Scarica la traccia in Pascal: passeggiata.pas

Scarica la traccia in Python: passeggiata.py

Scarica la traccia in VisualBasic: passeggiata.vb

Descrizione del problema

In una fresca giornata primaverile, Dario ha deciso di fare una passeggiata per il parco. Davanti a sé sono presenti $N$ tratti di strada, ciascuno dei quali è lungo $L_i$ passi.

Per compiere un passo Dario consuma un panino, quindi per percorrere l' $i$ -esimo tratto di strada Dario consuma $L_i$ panini.

"Panini"

All'inizio dell' $i$ -esimo tratto c'è un chiosco che vende panini ad un prezzo di $P_i$ monete l'uno. Lo zaino di Dario ha capienza infinita e ogni chiosco ha a disposizione un numero illimitato di panini, quindi Dario può a ogni chiosco comprare quanti panini vuole.

Quante monete spende al minimo Dario per arrivare alla fine degli $N$ tratti?

Formato di input

La prima riga del file di input contiene un intero $T$ , il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$ . Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

una riga contenente l'intero $N$ .
una riga contenente gli $N$ interi $L_{0}, \, \ldots, \, L_{N-1}$ .
una riga contenente gli $N$ interi $P_{0}, \, \ldots, \, P_{N-1}$ .

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura "Case #test: ", dove test è il numero del caso di test (a partire da $1$ ), seguita dall'intero a 64 bit $\mathtt{ris}$ .

Assunzioni

$T = 20$ , nei file di input che scaricherai saranno presenti esattamente $20$ casi di test.
$1 \leq N \leq 10^5$ .
$0 \leq L_i \leq 10^6$ .
$0 \leq P_i \leq 10^6$ .

Gruppi di testcase

I casi di test sono divisi in gruppi.
Ogni gruppo vale $5$ punti, e per ottenere il punteggio relativo ad esso è necessario risolvere correttamente tutti i casi di test che lo compongono.

Su alcuni gruppi valgono delle assunzioni aggiuntive:

$\small \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \texttt{Assunzioni} & \texttt{Gruppi} \\ \hline \text{Ogni } P_i \text{ ha lo stesso valore.} & 1 \\ \hline P_i \leq P_{i + 1} \text{ per ogni } i = 0 \ldots N - 2 & 2, 3 \\ \hline P_i \geq P_{i + 1} \text{ per ogni } i = 0 \ldots N - 2 & 4 \\ \hline N \leq 1000 & 5, 6, 7\\ \hline \text{Nessuna assunzione aggiuntiva} & 8, 9, 10 \\ \hline \end{array}$

Esempi di input/output

Input:

Output:

Case #1: 30
Case #2: 52

Spiegazione

Nel primo caso di esempio, Dario compra:

$5$ panini al chiosco $0$ per percorrere i tratti $0$ e $1$ ;
$5$ panini al chiosco $2$ per percorrere il tratto $2$ . In questo caso Dario spende $5 \cdot 4 + 5 \cdot 2 = 30$ monete.

Nel secondo caso di esempio, Dario compra:

$2$ panini al chiosco $0$ per percorrere il tratto $0$ ;
$10$ panini al chiosco $1$ per percorrere i tratti $1$ e $2$ ;
$4$ panini al chiosco $2$ per percorrere i tratti $3$ e $4$ . In questo caso Dario spende $2 \cdot 7 + 10 \cdot 3 + 4 \cdot 2 = 52$ monete.