how to approach the Farmer Frenzy problem?
here is my code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1010
ll cal_max(ll s[], ll m){
stack st;
ll a = INT_MIN;
ll i=0;
ll t;
while(i<m){
if(st.empty() || s[st.top()]<s[i] ){
st.push(i++);
}
else if(s[i]==s[st.top()])
continue;
else{
while (s[st.top()]>s[i] && st.empty()==false)
{
t = st.top();
st.pop();
a = max(a,s[t]*(st.empty() ? i : i - st.top() - 1));
}
}
}
return a;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,m;
cin>>n>>m;
ll arr[MAX][MAX];
ll sol[MAX];
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
cin>>arr[i][j];
}
}
ll ans = INT_MIN;
for(ll i=0;i<m;i++){
sol[i] = arr[0][i];
}
for(ll i=1;i<n;i++){
for(ll j=0;j<m;j++){
if(arr[i][j]==1){
sol[j]=sol[j]+1;
}
else
sol[j] = 0;
}
ans = max(ans,cal_max(sol,m));
}
cout<<ans<<"\n";
return 0;
}
please check it