随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #define MAXSIZE 100005
 5 int dp[MAXSIZE];
 6 int l[MAXSIZE],r[MAXSIZE];
 7 
 8 inline void scan(int &x){
 9     char ch;
10     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
11     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
12 }
13 
14 int main(){
15     //freopen("in.txt","r",stdin);
16     int t;
17     while (scanf("%d",&t),t){
18         int i;
19         for(i=1;i<=t;i++)
20             scan(dp[i]);
21         dp[0]=dp[t+1]=-1;
22         for(i=1;i<=t;i++)
23             l[i]=r[i]=i;
24         for(i=2;i<=t;i++)
25             while(dp[l[i]-1]>=dp[i])
26                 l[i]=l[l[i]-1];
27         for(i=t-1;i>=1;i--)
28             while(dp[r[i]+1]>=dp[i])
29                 r[i]=r[r[i]+1];
30         __int64 maxs=-1;
31         for(i=1;i<=t;i++)
32             if(maxs<(__int64)dp[i]*(r[i]-l[i]+1))
33                 maxs=(__int64)dp[i]*(r[i]-l[i]+1);
34         printf("%I64d\n",maxs);
35     }
36     return 0;
37 }
38 
posted on 2012-05-15 00:19 Leo.W 阅读(121) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理