首页 > 代码库 > Codeforces Round #221 (Div. 2) D
Codeforces Round #221 (Div. 2) D
有点郁闷的题目,给了2000ms,但是n,m的范围已经是5000了,5000 * 5000一般在别的OJ已经是超了2000ms,一开始不敢敲,看了下别人有n*m的潜逃循环,原来CF的机子如此的强大,一开始题意没看清错了,原来任意行可以交换,列不行
那就先dp出 每一行的 每一个位置包括它本身以及前面的连续出现1的长度,然后再对列进行处理,因为列是不能变的,所以对应列是固定的,那么就对列枚举,然后因为行可以交换,所以具体哪一列在哪一行可以变化,就把前面dp出的最大的放在最后面,意思就是呈现一个倒着放的梯形 当然也有可能是矩形,在中求一个面积最大的矩阵即可
int n,m; char mp[5000 + 55][5000 + 55]; int dp[5000 + 55][5000 + 55]; void init() { memset(mp,0,sizeof(mp)); memset(dp,0,sizeof(dp)); } bool input() { while(scanf("%d %d",&n,&m) == 2) { for(int i=1;i<=n;i++) scanf("%s",mp[i] + 1); return false; } return true; } void cal() { for(int i=1;i<=n;i++) { dp[i][0] = 0; for(int j=1;j<=m;j++) dp[i][j] = mp[i][j] == '1'?dp[i][j - 1] + 1:0; } int ans = 0; for(int j=1;j<=m;j++) { int tmp[5000 + 55]; for(int i=1;i<=n;i++)tmp[i] = dp[i][j]; sort(tmp + 1,tmp + n + 1); for(int i=1;i<=n;i++)ans =max(ans,tmp[i] * (n - i + 1)); } cout<<ans<<endl; } void output() { } int main () { while(true) { init(); if(input())return 0; cal(); output(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。