题意:给出数组a,b,组成矩阵c,其中$c_{ij}=a_i*b_j$,找出最的大子矩阵,使得矩阵元素和<=x,求这个矩阵的size

n,m<=2000

思路:对于子矩阵(l1...r1)*(l2...r2),矩阵元素和为(a[l1]+a[l1+1]+...+a[r1])*(b[l2]+b[l2+1]+...+b[r2])

这样处理出长度为i的连续数组最小和aa[i],bb[i],再枚举一下长度即可

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
//#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = ;
const int maxn = 2e5+;
const int maxm = 2e5+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); ll a[maxn],b[maxn];
ll aa[maxn], bb[maxn];
int main() {
int n, m;
scanf("%d %d", &n, &m);
mem(a, );
mem(b, );
for(int i = ; i <= n; i++){
scanf("%lld", &a[i]);
a[i]+=a[i-];
}
for(int i = ; i <= m; i++){
scanf("%lld", &b[i]);
b[i]+=b[i-];
}
ll ans = ;
ll tmp = ;
ll x;
scanf("%lld", &x);
mem(aa,0x3f);
mem(bb,0x3f);
for(int i = ; i <= n; i++){
for(int j = ; j <= i; j++){
//j~i
aa[i-j+]=min(aa[i-j+],a[i]-a[j-]);
}
}
for(int i = ; i <= m; i++){
for(int j = ; j <= i; j++){
bb[i-j+]=min(bb[i-j+],b[i]-b[j-]);
}
} for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
if(aa[i]*bb[j]<=x)ans = max(ans, 1ll*i*j);
}
}
printf("%lld", ans);
return ;
}

最新文章

  1. 【非原创】IOS 验证文字是否是中文
  2. 知乎布局||offsetTop||侧边栏自动等高
  3. 编译x264 for ios
  4. springmvcの神总结のreadme
  5. Linux crond定时任务
  6. Web开发中设置快捷键来增强用户体验
  7. MHA 安装过程 原创
  8. 微信小程序正式发布!这是最全的上手指南
  9. angular 实现左侧和顶部固定定位布局
  10. HDU 4786 Fibonacci Tree 最小生成树
  11. Linux 添加程序图标到开始菜单中
  12. 从item-base到svd再到rbm,多种Collaborative Filtering(协同过滤算法)从原理到实现
  13. CStringArray error C2248: &#39;CObject::CObject&#39; : cannot access private member declared in class
  14. Hibernate(二)持久化对象的状态
  15. c++ 重载、重写、重定义(隐藏)
  16. sqlmap tamper编写
  17. centos5.5 快速安装mysql
  18. axios简单介绍
  19. DSP5509之采样定理
  20. NGUI 3.50 UIButton使用

热门文章

  1. docker-覆盖网络
  2. Exceptionless运用结果
  3. list绑定
  4. 日志查看工具 logviewer pro的使用
  5. 数据结构与算法 Python语言实现 第一章练习
  6. Spring Boot2 系列教程(一) | 如何使用 IDEA 构建 Spring Boot 工程
  7. dp-最大连续子序列的和
  8. Go Web 编程之 数据库
  9. openjudge 拯救公主
  10. SpringBoot_Web开发_定制错误数据