poj 3494

poj 2796

poj 2082 题目链接

## poj 1964 City Game(单调栈，输入挂)

poj 1964

poj竟然也卡读入。。。人性呢。。。。

(i,j)点所在的矩形面积就是 (r[i][j]-l[i][j]+1)*a[i][j];

## poj 3250 Bad Hair Day(单调栈)

poj 3250

n头牛排成一列，第n只牛在最前面，第1只牛在最后面。第i只牛能看到的牛的个数是，它前面的且没有被其他牛遮挡的牛的个数，遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。

poj 2559

## 1660: [Usaco2006 Nov]Bad Hair Day 乱发节

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 872  Solved: 415
[Submit][Status][Discuss]

## Input

* Line 1: 牛的数量 N。

* Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。

## Output

* Line 1: 一个整数表示c[1] 至 c[N]的和。

6
10
3
7
4
12
2

5

3+0+1+0+1=5

## 1657: [Usaco2006 Mar]Mooo 奶牛的歌声

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 634  Solved: 447
[Submit][Status][Discuss]

## Description

Farmer John’s N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.

Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000)，叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会 被0，1，2头奶牛听到（这取决于它的两边有没有比它高的奶牛）。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后，Farmer John打算买一个耳罩给被残害得最厉 害的奶牛，请你帮他计算最大的总音量。

## Input

* Line 1: A single integer, N.

* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.

## Output

* Line 1: The loudest moo volume heard by any single cow.

## Sample Input

3
4 2
3 5
6 10

INPUT DETAILS:

Three cows: the first one has height 4 and moos with volume 2, etc.

7

Silver

## 1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 396  Solved: 317
[Submit][Status][Discuss]

## Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

6

## codeforces 442C. Artem and Array

C. Artem and Array
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn’t have an adjacent number to the left or right, Artem doesn’t get any points.

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai(1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Sample test(s)
input

output

input

output

input

output