洛谷 P1565 牛宫

题目：牛宫

思路：
咳咳，先放个提交记录……
嗯再来个mjy0724的思路：

然后就没我什么事了
有这么几点需要注意的地方：
1、vector一定不能作为参数传进函数，会T到飞起，亲测100->50
2、第一列数要单独判断
3、前缀和的处理，[i,j]的字段和大于0的条件是sum[j]>sum[i-1]而非sum[j]>sum[i]
4、要用long long

数据生成器：

#include<bits/stdc++.h>
using namespace std;

#define maxn 100
#define maxk 100
#define Rand() (rand()+rand()%19260817)

int n,m,r,k;

int main() {
    srand(time(NULL));
    n=Rand()%maxn+1;
    m=Rand()%maxn+1;
    printf("%d %d\n",n,m);
    for(int i=1; i<=n; i++) {
        for(int i=1; i<=m; i++) printf("%d ",(Rand()%maxk+1)*((rand()&1)?1:-1));
        printf("\n");
    }

    return 0;
}

代码：

#include<bits/stdc++.h>
using namespace std;

#define maxn 200
#define ll long long

ll n,m;
ll a[maxn+5][maxn+5]= {0};

ll c[maxn+5][maxn+5]= {0};
ll sum[maxn+5]= {0};

void readin() {
    scanf("%lld%lld",&n,&m);
    for(ll i=1; i<=n; i++) {
        for(ll j=1; j<=m; j++) {
            scanf("%lld",&a[i][j]);
            c[i][j]=c[i-1][j]+a[i][j];
        }
    }
}

vector<ll> vec;

ll binsearch(ll x) {
    ll l=0,r=vec.size()-1;
    while(l+1<r) {
        ll mid=l+(r-l)/2;
        if(sum[vec[mid]]<x) r=mid;
        else l=mid;
    }
    if(l>=1&&sum[vec[l-1]]<x) return l-1;
    if(sum[vec[l]]>=x) return l+1;
    return l;
}

ll slv() {
    ll ans=0;
    for(ll i=1; i<=n; i++) {
        for(ll j=i; j<=n; j++) {
            ll h=j-i+1;
            for(ll k=1; k<=m; k++) {
                sum[k]=sum[k-1]+c[j][k]-c[i-1][k];
            }
            if(sum[1]>0) ans=max(ans,h);
            vec.clear();
            vec.push_back(1);
            for(ll k=2; k<=m; k++) {
                ll x=binsearch(sum[k]);
                if(sum[k]<sum[vec[vec.size()-1]]) vec.push_back(k);
                if(sum[k]>0) ans=max(ans,h*k);
                else {
                    if(x>=vec.size()||vec[x]>=k||sum[vec[x]]>=sum[k]) continue;
                    ans=max(ans,h*(k-vec[x]));
                }
            }
        }
    }
    return ans;
}

int main() {
    readin();
    ll ans=slv();
    printf("%lld",ans);
    return 0;
}