| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
单调队列,wa了好几发。。。。AC代码AC代码 #include <cstdio> #include <algorithm> #include <iostream> #define int long long using namespace std; typedef pair<int,int> P; const int MAX = 100010; int arr[MAX]; P que[MAX]; int sum[MAX]; int l,r; int N; void solve() { for(int i = 0;i < N;i++) {scanf("%lld",&arr[i]);sum[i+1] = sum[i] + arr[i];} if(N==1) { cout<<arr[0]*arr[0]<<endl<<1<<' '<<1<<endl; return; } arr[N] = 0; sum[N+1] = sum[N]; l = 0;r = 1; que[0] = (P){arr[0],0}; int ans = 0; int ansl = 1,ansr = 1; for(int i = 1;i <= N;i++) { while(r > l && que[r-1].first > arr[i]) { r--; if(r-1 >= 0) { int na = que[r].first*(sum[i]- sum[que[r-1].second+1]); if(na > ans) { ans = na; ansl = que[r-1].second+2; ansr = i; } } else { int na = que[r].first*(sum[i]); if(na > ans) { ans = na; ansl = 1; ansr = i; } } } que[r++] = (P){arr[i],i}; } cout<<ans<<endl; cout<<ansl<<' '<<ansr<<endl; } main() { while(~scanf("%lld",&N)) { solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator