Codeforces Round #221 (Div. 2) D
Codeforces div round
2023-09-11 14:20:43 时间
有点郁闷的题目,给了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(); } }
相关文章
- Codeforces Round #277(Div. 2) (A Calculating Function, B OR in Matrix, C Palindrome Transformation)
- 【Educational Codeforces Round 48 (Rated for Div. 2) D】Vasya And The Matrix
- 【Codeforces Round #499 (Div. 1) B】Rocket
- 【Codeforces Round #460 (Div. 2) B】 Perfect Number
- 【Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) A】 Perfect Squares
- 【Codeforces Round #445 (Div. 2) B】Vlad and Cafes
- 【Codeforces Round #442 (Div. 2) B】Nikita and string
- 【Codeforces Round #437 (Div. 2) B】Save the problem!
- 【Codeforces Round #432 (Div. 2) A】 Arpa and a research in Mexican wave
- 【Codeforces Round #428 (Div. 2) B】Game of the Rows
- 【Codeforces Round #427 (Div. 2) C】Star sky
- 【Codeforces Round #424 (Div. 2) D】Office Keys
- 【Codeforces Round #422 (Div. 2) C】Hacker, pack your bags!(hash写法)
- Codeforces Round #FF (Div. 1)-A,B,C
- Codeforces Round #265 (Div. 2) C. No to Palindromes! 构建无回文串子
- Codeforces Round #263
- Codeforces Round #FF (Div. 1) B. DZY Loves Modification
- Codeforces Round #107 (Div. 2)---A. Soft Drinking
- Codeforces Round #466 (Div. 2)
- Codeforces Round #429 (Div. 2)
- Codeforces Round #428 (Div. 2)
- Codeforces Round #307 (Div. 2)
- Codeforces Round #419 (Div. 2)