INSULENG - Insulation
Give N bricks and a sequence a1...an as the insulation of them. If we arrange the bricks in that order into a wall then the insulation of the wall is a1 + a2 + ... + aN + max(0, a2 - a1) + max(0, a3 - a2) + ... + max(0, aN - aN - 1). Your task is to arrange the bricks so that the insulation of the wall is maximum.
Input
- The first line is N (1 <= N <= 105).
- In each of the next N lines, the ith line is ai-1
Output
- The maximum insulation of the wall.
Example
Input:
4
5
4
1
7 Output:
24
hide comments
Mitch Schwartz:
2011-11-04 03:45:54
Input is poorly formatted. |
|
Egor:
2011-03-18 13:26:03
greed! |
|
:D:
2011-03-15 11:08:16
I think this problems is set as a challenge (my score for challenges isn't adding up). Please correct that. |
|
T-7:
2011-03-15 07:56:05
The example is 24 if we arrange the bricks like this: 1 5 4 7 ;) |
|
Eduardo Carrasquero:
2011-03-15 04:53:07
the example is 23 for me...
|
|
cegprakash:
2011-03-14 17:53:38
i think such test cases went for me to TLE
|
|
:D:
2011-03-14 17:25:44
How did you checked all permutations for N=10^5 :O |
|
Sushovan Sen:
2011-03-14 17:08:05
I dont understand scoring.. |
|
Kashyap Krishnakumar:
2011-03-14 15:53:22
@cegprakash: you need not check for all permutations! :P |
Added by: | Hacker7 |
Date: | 2011-03-14 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE |
Resource: | VNOI |