ARC 081 F Flip and Rectangles(700)

最大長方形

2 x 2マスの部分を見ると解法が自明だが、強実装で辛い

障害がマスではなく点の最大長方形問題になる

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define lol(i,n) for(int i=0;i<n;i++)
6. #define mod 1000000007
7. typedef long long ll;
8. using namespace std;
9. int dp[2010];
10. int c[2010][2010];
11. #include<stack>
12. int BiggestRectangle(int N,int buf[]){
13. buf[N]=0;
14. stack<pair<int,int> >st;
15. int ret=0;
16. for(int i=0;i<=N;i++){
17. if(st.empty())st.push(make_pair(buf[i],i));
18. else if(st.top().first<buf[i])st.push(make_pair(buf[i],i));
19. else if(st.top().first>buf[i]){
20. int pnt=i;
21. while(!st.empty()){
22. int height=st.top().first;
23. int index=st.top().second;
24. if(height<buf[i])break;
25. st.pop();
26. ret=max(ret,height*(i-index+1));
27. pnt=index;
28. }
29. st.push(make_pair(buf[i],pnt));
30. }
31. }
32. return ret;
33. }
34. int main(){
35. int h,w;
36. cin>>h>>w;
37. lol(i,h){
38. lol(j,w){
39. char z;cin>>z;
40. if(z=='.')c[i][j]=0;
41. if(z=='#')c[i][j]=1;
42. }
43. }
44. for(int i=0;i<h-1;i++){
45. for(int j=0;j<w-1;j++){
46. int tmp=c[i][j]+c[i+1][j];
47. tmp+=c[i][j+1]+c[i+1][j+1];
48. c[i][j]=tmp%2;
49. }
50. }
51. int ans=max(h,w);
52. for(int j=0;j<w-1;j++)dp[j]=1;
53. for(int i=0;i<h-1;i++){
54. for(int j=0;j<w-1;j++){
55. if(c[i][j]==true)dp[j]=1;
56. else dp[j]++;
57. }
58. ans=max(ans,BiggestRectangle(w-1,dp));
59. }
60. cout<<ans<<endl;
61. return 0;
62. }

部分問題は2つセットの場合がある