Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 改单调栈为什么re了呀

Posted by qq2567722641 at 2019-10-02 14:47:57 on Problem 3494
```#include<iostream>
#include<cstring>
using namespace std;

const int maxn=2000+20;
int a[maxn][maxn],w[maxn];
struct Stack{
int top;
int data[maxn];
Stack(){top=-1;}
};

int ans;
void push(Stack *stack,int x){
if(stack->empty()||x>stack->data[stack->top]){
stack->data[++stack->top]=x;
w[stack->top]=1;
}else{
int wid=0;
while(!stack->empty()&&x<=stack->data[stack->top]){
wid+=w[stack->top];
ans=max(ans,wid*stack->data[stack->top]);
stack->top--;
}
stack->data[++stack->top]=x;
w[stack->top]=wid+1;
}
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
ans=0;
memset(w,0,sizeof(w));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&a[i][j]);
}
}
int k,k1;
for(int i=0;i<n;i++){
int cnt=1;
for(int j=0;j<n;j++){
if(a[j][i]==1){
a[j][i]=cnt++;
}else if(a[j][i]==0){
cnt=1;
}
if(cnt>k){
k=cnt;k1=j;
}
}
}
Stack *stack=new Stack();
for(int i=0;i<n;i++){
push(stack,a[k1][i]);
}
push(stack,0);
printf("%d\n",ans);
}
} ```

Followed by: