2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4 [2021/04/30 18:32] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4 [2021/04/30 18:55] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 379: | 行 379: | ||
| } | } | ||
| enter(ans); | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | <hidden 分治版本> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e6+5; | ||
| + | int h[MAXN],a[MAXN],b[MAXN]; | ||
| + | LL cal(int l,int r){ | ||
| + | return 1LL*(h[a[r]]+h[b[l]])*(a[r]-b[l]); | ||
| + | } | ||
| + | LL solve(int ql,int qr,int sl,int sr){ | ||
| + | if(ql>qr)return 0; | ||
| + | LL ans=-1; | ||
| + | int qmid=ql+qr>>1,smid; | ||
| + | _rep(i,sl,sr){ | ||
| + | if(ans<cal(i,qmid)){ | ||
| + | ans=cal(i,qmid); | ||
| + | smid=i; | ||
| + | } | ||
| + | } | ||
| + | return max(ans,max(solve(ql,qmid-1,sl,smid),solve(qmid+1,qr,smid,sr))); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),qcnt=0,mcnt=0; | ||
| + | _rep(i,1,n)h[i]=read_int(); | ||
| + | _rep(i,1,n){ | ||
| + | while(qcnt&&h[a[qcnt]]<=h[i])qcnt--; | ||
| + | a[++qcnt]=i; | ||
| + | if(mcnt==0||h[b[mcnt]]<h[i]) | ||
| + | b[++mcnt]=i; | ||
| + | } | ||
| + | enter(solve(1,qcnt,1,mcnt)); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/2021_buaa_spring_training4.1619778749.txt.gz · 最后更改: 2021/04/30 18:32 由 jxm2001
