Codeforces 1060C Maximum Subrectangle(子矩阵+预处理)
2024-09-05 16:28:53
题意:给出数组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 ;
}
最新文章
- 【非原创】IOS 验证文字是否是中文
- 知乎布局||offsetTop||侧边栏自动等高
- 编译x264 for ios
- springmvcの神总结のreadme
- Linux crond定时任务
- Web开发中设置快捷键来增强用户体验
- MHA 安装过程 原创
- 微信小程序正式发布!这是最全的上手指南
- angular 实现左侧和顶部固定定位布局
- HDU 4786 Fibonacci Tree 最小生成树
- Linux 添加程序图标到开始菜单中
- 从item-base到svd再到rbm,多种Collaborative Filtering(协同过滤算法)从原理到实现
- CStringArray error C2248: &#39;CObject::CObject&#39; : cannot access private member declared in class
- Hibernate(二)持久化对象的状态
- c++ 重载、重写、重定义(隐藏)
- sqlmap tamper编写
- centos5.5 快速安装mysql
- axios简单介绍
- DSP5509之采样定理
- NGUI 3.50 UIButton使用