2019牛客暑期多校训练营 第二场

 A.Eddy Walker

B.Eddy Walker 2

 C.Go on Strike!

 D.Kth Minimum Clique

 E.MAZE

F.Partition problem

 G.Polygons

 H.Second Large Rectangle

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2000;
 4 int n,m,k,l[N],r[N],h[N],a[N*N],ans,kk;
 5 char s[N][N];
 6 int main() {
 7     scanf("%d%d", &n, &m);
 8     for (int j=0;j<m;j++){
 9             l[j]=-1;
10             r[j]=m;
11     }
12     set< pair<pair<int, int>, int> > ss;
13     for (int i = 0; i < n; i++) {
14         scanf("%s", &s[i]);
15         k = -1;
16         for (int j = 0; j < m; j++) {
17             l[j] = max(k, l[j]);
18             if (s[i][j] == '1') {
19                 h[j]++;
20             } else {
21                 h[j] = 0;
22                 l[j] = -1;
23                 k = j;
24             }
25         }
26         k = m;
27         for (int j = m - 1; j >= 0; j--) {
28             r[j] = min(r[j], k);
29             if (s[i][j] == '0') {
30                 k = j;
31                 r[j] = m;
32             }
33         }
34         ss.clear();
35         for (int j = 0; j < m; ++j) {
36             ss.insert(make_pair(make_pair(l[j], r[j]), h[j]));
37         }
38         for (auto item : ss) {
39             a[++kk] = item.second * (item.first.second - item.first.first - 1);
40             a[++kk] = item.second * (item.first.second - item.first.first - 2);
41             a[++kk] = (item.second - 1) * (item.first.second - item.first.first - 1);
42         }
43     }
44     sort(a+1, a+kk+1 ,greater<int>());
45     printf("%d
",max(0,a[2]));
46 }
View Code

I.Inside A Rectangle

 J.Subarray

原文地址:https://www.cnblogs.com/Accpted/p/11218501.html