专栏首页Zaqdt_ACMCodeforces Round #513 C. Maximum Subrectangle(思维)

Codeforces Round #513 C. Maximum Subrectangle(思维)

题目链接:http://codeforces.com/contest/1060/problem/C

       题意是输入n和m两组数,再输入一个值x,由这两组数组成一个n*m的矩阵a[i][j]表示a[i]*b[j]的值,在这个矩阵中找子矩阵,使得该子矩阵中所有的元素之和小于等于x,问所有符合条件的子矩阵中,面积最大的是多少。

       思路就是维护一个前缀和,然后去更新长度为1,2,3...n的子数组的和的最小值,然后联系两个数组遍历矩阵求解,直接看呆码吧...


AC代码:

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 20005
using namespace std;
ll a[maxn],b[maxn],_a[maxn],_b[maxn];
int n,m,x;

int main()
{
	scanf("%d%d",&n,&m);
	a[0] = 0; b[0] = 0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i] += a[i-1];
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]),b[i] += b[i-1];
	scanf("%d",&x);
	for(int i=1;i<=n;i++){
		_a[i] = inf;
		for(int j=i;j<=n;j++){
			_a[i] = min(_a[i], a[j] - a[j - i]);
		}
	}
	for(int i=1;i<=m;i++){
		_b[i] = inf;
		for(int j=i;j<=m;j++){
			_b[i] = min(_b[i], b[j] - b[j - i]);
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(_a[i] * _b[j] <= x){
				ans = max(ans, i * j);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #514 (Div. 2) B. Forgery(思维+暴力)

    题目链接:http://codeforces.com/contest/1059/problem/B

    Ch_Zaqdt
  • CodePlus 第五次网络赛 我有矩阵,你有吗?(思维+枚举)

    题目链接:https://oj.thusaac.org/#!/contest/136/problem/2   (要报名才能看题交题)

    Ch_Zaqdt
  • HDU 4185 Oil Skimming(思维+二分图最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4185

    Ch_Zaqdt
  • HDU 6514 Monitor 二维前缀和

    用户2965768
  • hdu-----(2807)The Shortest Path(矩阵+Floyd)

    The Shortest Path Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/...

    Gxjun
  • 斯坦纳树小结

    attack
  • 04:最匹配的矩阵

    04:最匹配的矩阵 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个m*n的矩阵A和r*s的矩阵B,其中0 < r ≤ m, 0 < s...

    attack
  • 2011 Google Code Jam 小记

    好久没写这种类型的代码,感觉真是退步了很多。 这是我第一次参加Google Code Jam,以前有过报名可是没有做过。 我发现Google Code Ja...

    owent
  • 08:矩阵加法

    08:矩阵加法 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个n行m列的矩阵A和B,输出它们的和A+B。 输入第一行包含两个整数n和...

    attack
  • C语言经典习题100例(八)36-40

    实现思路: 利用双重for循环控制输入二维数组,再将i和j相同的数组元素累加后输出。

    cutercorley

扫码关注云+社区

领取腾讯云代金券