Android progress bar style

2022-12-30   ES  

1657: [USACO2006 Mar] The singing of Moo Dairy Cow

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 537  Solved: 374



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’s n (1 <= n <= 50,000) The cow stands neatly into a column of “howling”. Each cow has a certain height H (1 <= h <= 2000000000), and the volume of the call is v (1 <= v <= 10000). Each cow’s call spreads to both ends, but in each direction, it will only be heard by a nearest cow that is greater than its nearest height, so each call will only be heard by 0, 1,2 dairy cows hear (This depends on whether there is a tall cow on both sides). The total volume that a cow hears is the sum of all the volume it hear. Since some dairy cows have suffered huge volume, Farmer John intends to buy an earmuffs to the most harmful cow, please help him calculate the largest total volume.


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

Line 1: A positive integer n.

No. 2 to N+1 line: Each row includes two integers separated by spaces, which represent the height of the cow standing in the i -i -i -i -statally stand in the team and the volume of her singing when singing.


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

The highest total volume of dairy cows in the team.

The 3rd cow in the

Sample Input

4 2
3 5
6 10


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

Sample Output



 team can hear the singing of the first and second cows, so the total volume she can hear is 2+5 = 7. Although her volume was 10 when she sang, there was no cow to hear her singing.


Monoly queue optimized DP.

Do you can do it once.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,h[50005],v[50005],q[50005],ans[50005];
int main()
	for (int i=1;i<=n;i++)
	int l=1,r=1;
	for (int i=2;i<=n;i++)
		int k=r;
		while (k>l&&h[q[k]]<h[i])
		if (h[q[k]]>h[i])
		while (r>=l&&h[q[r]]<=h[i])
	for (int i=n-1;i>=1;i--)
		int k=r;
		while (k>l&&h[q[k]]<h[i])
		if (h[q[k]]>h[i]) 
		while (r>=l&&h[q[r]]<=h[i])
	int ma=0;
	for (int i=1;i<=n;i++)
	return 0;


1. Consider the water questions and write clearly. Every time you look for the first number larger than the current, so find it in the queue.


Related Posts

— SPREAD > Tidyr :: SPREAD (Spread + data = mydata1, + key = year, + value = sale +) name address sale2014 sale2015 sale2016 sale2017 1 Store1 Putuo District 3000 3020 5150 4450 2 Store2 Huangpu District 2500 2800 3600 4100 3 Store3 Xuhui District 2100 3900 2700 4000 4 Store4 Pudong New District 1000 2000 2500 3200

Dynamic library and static library under ubuntu

MATLAB three -bit curve plot3 function

multi -step progress bar implementation method

Android progress bar style

Random Posts

python execute timing task LTC

Machine Learning Basics

Spring Tags to add attributes to the object through the Property tag

BZOJ2190: [SDOI2008] Guardian (Euler function) Hanks

How to design your own dialog in QML applications