前缀和+一堆优化是否可以逆天改命?(不使用悬线和单调栈等)
  • 板块P4147 玉蟾宫
  • 楼主lrhtom
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/8 20:50
  • 上次更新2023/10/23 13:38:01
查看原帖
前缀和+一堆优化是否可以逆天改命?(不使用悬线和单调栈等)
837535
lrhtom楼主2023/6/8 20:50
#include <iostream>
#include<algorithm>
#include <set>
#include<stack>
#include <immintrin.h>
#pragma GCC target("avx,avx2")
using namespace std;
int a[1010][1010];
int tm=0;
int n,m;
int mj(int y,int x) {
	for(int i=1; i<=n-y+1; i++) {
		for(int i2=1; i2<=m-x+1; i2++) {
			if(a[i+y-1][i2+x-1]+a[i-1][i2-1]-a[i+y-1][i2-1]-a[i-1][i2+x-1]==0) {
				return 0;
			}
		}
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	int aws=0;
	char c;
	int j=0;
	int sz=n*m;
	for(int i=1; i<=n; i++) {
		for(int i2=1; i2<=m; i2++) {
			cin>>c;
			if(c=='R') {
				a[i][i2]=1;
				j++;
			}
			a[i][i2]+=a[i-1][i2]+a[i][i2-1]-a[i-1][i2-1];
		}
	}
	if(j==0) {
		cout<<3*sz;
	} else {
		int minsz=0;
		if(n<m) {
			minsz=n*(j/n+(j%n==0?0:1));
		} else {
			minsz=m*(j/m+(j%m==0?0:1));
		}
		minsz=sz-minsz;
		for(int i=1; i<=n; i++) {
			for(int i2=1; i2<=m; i2++) {
				if(aws<i*i2&&i*i2<=minsz) {
					if(mj(i,i2)==0) {
						aws=max(aws,i*i2);
					}
				}
			}
		}
		cout<<aws*3;
	}
	return 0;
}

基本上除了快读感觉优化的差不多了55分

是否存在ac方法

2023/6/8 20:50
加载中...