C. Maximum Subrectangle

链接

[http://codeforces.com/contest/1060/problem/C]

题意

给你两个数列，可以构成一个矩阵C,ci,j=ai⋅bj 1≤x1≤x2≤n , 1≤y1≤y2≤m

还有一个x,让你求一个子矩阵，使得矩阵元素和小于等于x，面积最大

分析

贪心，思维，只需要求出前缀和，还有长度为i,时子窜和最小

具体看代码

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=2e3+5;

ll a[N],b[N];

int main(){

	ios::sync_with_stdio(false);

	 cin.tie(0); cout.tie(0);

	//freopen("in.txt","r",stdin);

	ll n,m,x;

	while(cin>>n>>m){

		ll sum1[N],sum2[N],mi1[N],mi2[N];

		memset(mi1,0x3f,sizeof(mi1)); memset(mi2,0x3f,sizeof(mi2));

		for(int i=1;i<=n;i++) {

			cin>>a[i];

			sum1[i]=sum1[i-1]+a[i];//统计单个列的前缀和

		}

		 for(int i=1;i<=m;i++)

		  {

		  	  cin>>b[i];

			  sum2[i]=sum2[i-1]+b[i];//统计单个列的前缀和

		  }

		  cin>>x;

		for(int i=1;i<=n;i++){

			for(int j=0;i+j<=n;j++){

				mi1[i]=min(mi1[i],sum1[i+j]-sum1[j]);//长度为i的最小值为多少

			}

		}

		for(int i=1;i<=m;i++){

			for(int j=0;i+j<=m;j++){

				mi2[i]=min(mi2[i],sum2[i+j]-sum2[j]);//长度为i的最小值为多少

			}

		}

		int ans=0;

		for(int i=1;i<=n;i++){

			for(int j=1;j<=m;j++){

				if(mi1[i]*mi2[j]<=x) ans=max(ans,i*j);//贪心 ,因为mi1和mi2都是长度分别为i,j时，和最小的

				//使得相同i,j情况下 ，mi1[i]*mi2[j]尽可能小

			}

		}

		cout<<ans<<endl;

	}

	return 0;

}