QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391017#7448. rfplcaLynkcatWA 1ms5996kbC++177.0kb2024-04-16 11:27:092024-04-16 11:27:10

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 11:27:10]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：5996kb
查看
  • [2024-04-16 11:27:09]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e9
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
//#define N
using namespace std;
const int N=105;
int n,a[N][N],s[N][N],ss[N][N];
int f[N][N],g[N][N];
int pre[N],suf[N];
int F[N][N][N];
//l L R 
int query(int x,int y,int X,int Y)
{
	return ss[X][Y]-ss[x-1][Y]-ss[X][y-1]+ss[x-1][y-1];
}
void BellaKira()
{
	cin>>n;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			a[i][j]=c-'0';
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			ss[i][j]=(ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]+((a[i][j]==0)?1:-1));
		}
	int ans=s[n][n];
	for (int l=1;l<=n;l++)
		for (int r=l;r<=n;r++)
		{
			for (int i=0;i<=n+1;i++)
				for (int j=0;j<=n+1;j++) f[i][j]=-inf,g[i][j]=-inf;
			for (int y=1;y<=n;y++)
			{
				int mx=-inf;
				for (int i=1;i<=y;i++)
				{
					if (r-(y-i)>=1&&r-(y-i)<=l) 
						mx=max(mx,query(i,r-(y-i),y,r));
					f[i][y]=mx;
					ans=max(ans,s[n][n]+mx);
				}
				mx=-inf;
				for (int i=n;i>=y;i--)
				{
					if (l+(i-y)<=n&&l+(i-y)>=r)
						mx=max(mx,query(y,l,i,l+(i-y)));
					g[y][i]=mx;
					ans=max(ans,s[n][n]+mx);
				}
			}
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					ans=max(ans,s[n][n]+f[i][j]+g[i][j]-2*query(i,l,j,r));
				}
			for (int i=1;i<=n;i++)
				for (int j=n;j>=1;j--)
					f[i][j]=max(f[i][j],f[i][j+1]);
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++) g[i][j]=max(g[i][j],g[i-1][j]);
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					if (l+(j-i)>=r&&l+(j-i)<=n)
					{
						ans=max(ans,s[n][n]+f[i][j]-2*query(i,l,j,r)
						+query(i,l,j,l+(j-i)));
					}
					if (r-(j-i)<=l&&r-(j-i)>=1)
					{
						ans=max(ans,s[n][n]+g[i][j]-2*query(i,l,j,r)
						+query(i,r-(j-i),j,r));
					}
				}
		}
	// Reverse
	for (int i=1;i<n-i+1;i++)
	{
		for (int j=1;j<=n;j++) swap(a[i][j],a[n-i+1][j]);
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			ss[i][j]=(ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]+((a[i][j]==0)?1:-1));
		}
	for (int l=1;l<=n;l++)
		for (int r=l;r<=n;r++)
		{
			for (int i=0;i<=n+1;i++)
				for (int j=0;j<=n+1;j++) f[i][j]=-inf,g[i][j]=-inf;
			for (int y=1;y<=n;y++)
			{
				int mx=-inf;
				for (int i=1;i<=y;i++)
				{
					if (r-(y-i)>=1&&r-(y-i)<=l) 
						mx=max(mx,query(i,r-(y-i),y,r));
					f[i][y]=mx;
					ans=max(ans,s[n][n]+mx);
				}
				mx=-inf;
				for (int i=n;i>=y;i--)
				{
					if (l+(i-y)<=n&&l+(i-y)>=r)
						mx=max(mx,query(y,l,i,l+(i-y)));
					g[y][i]=mx;
					ans=max(ans,s[n][n]+mx);
				}
			}
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					ans=max(ans,s[n][n]+f[i][j]+g[i][j]-2*query(i,l,j,r));
				}
			for (int i=1;i<=n;i++)
				for (int j=n;j>=1;j--)
					f[i][j]=max(f[i][j],f[i][j+1]);
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++) g[i][j]=max(g[i][j],g[i-1][j]);
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					if (l+(j-i)>=r&&l+(j-i)<=n)
					{
						ans=max(ans,s[n][n]+f[i][j]-2*query(i,l,j,r)
						+query(i,l,j,l+(j-i)));
					}
					if (r-(j-i)<=l&&r-(j-i)>=1)
					{
						ans=max(ans,s[n][n]+g[i][j]-2*query(i,l,j,r)
						+query(i,r-(j-i),j,r));
					}
				}
		}
	// T
	for (int i=1;i<=n;i++)
		for (int j=1;j<i;j++)
			swap(a[i][j],a[j][i]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			ss[i][j]=(ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]+((a[i][j]==0)?1:-1));
		}
	for (int l=1;l<=n;l++)
		for (int r=l;r<=n;r++)
		{
			for (int i=0;i<=n+1;i++)
				for (int j=0;j<=n+1;j++) f[i][j]=-inf,g[i][j]=-inf;
			for (int y=1;y<=n;y++)
			{
				int mx=-inf;
				for (int i=1;i<=y;i++)
				{
					if (r-(y-i)>=1&&r-(y-i)<=l) 
						mx=max(mx,query(i,r-(y-i),y,r));
					f[i][y]=mx;
					ans=max(ans,s[n][n]+mx);
				}
				mx=-inf;
				for (int i=n;i>=y;i--)
				{
					if (l+(i-y)<=n&&l+(i-y)>=r)
						mx=max(mx,query(y,l,i,l+(i-y)));
					g[y][i]=mx;
					ans=max(ans,s[n][n]+mx);
				}
			}
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					ans=max(ans,s[n][n]+f[i][j]+g[i][j]-2*query(i,l,j,r));
				}
			for (int i=1;i<=n;i++)
				for (int j=n;j>=1;j--)
					f[i][j]=max(f[i][j],f[i][j+1]);
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++) g[i][j]=max(g[i][j],g[i-1][j]);
			for (int i=1;i<=n;i++)
				for (int j=i;j<=n;j++)
				{
					if (l+(j-i)>=r&&l+(j-i)<=n)
					{
						ans=max(ans,s[n][n]+f[i][j]-2*query(i,l,j,r)
						+query(i,l,j,l+(j-i)));
					}
					if (r-(j-i)<=l&&r-(j-i)>=1)
					{
						ans=max(ans,s[n][n]+g[i][j]-2*query(i,l,j,r)
						+query(i,r-(j-i),j,r));
					}
				}
		}
		
	// x | x
	// for (int i=1;i<=n;i++)
	// {
		// for (int j=1;j<=n;j++) cout<<a[i][j];
		// cout<<'\n';
	// }
	for (int i=0;i<=n;i++) pre[i]=s[n][i];
	for (int i=n+1;i>=1;i--) suf[i]=s[n][n]-s[n][i-1]; 
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			for (int k=0;k<min(i,j);k++)
			{
				pre[j]=max(pre[j],s[n][j]+query(i-k,j-k,i,j));
				suf[j-k]=max(suf[j-k],s[n][n]-s[n][j-k-1]+query(i-k,j-k,i,j));
			}
		}
	for (int i=1;i<=n;i++) pre[i]=max(pre[i],pre[i-1]+s[n][i]-s[n][i-1]);
	for (int i=n;i>=1;i--) suf[i]=max(suf[i],suf[i+1]+s[n][i]-s[n][i-1]);
	for (int i=0;i<=n;i++)
	{
		ans=max(ans,pre[i]+suf[i+1]);
		// cout<<i<<" "<<pre[i]<<" "<<suf[i+1]<<endl;
	}
	//x_x
	for (int i=0;i<=n;i++) pre[i]=s[i][n];
	for (int i=n+1;i>=1;i--) suf[i]=s[n][n]-s[i-1][n]; 
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			for (int k=0;k<min(i,j);k++)
			{
				pre[i]=max(pre[i],s[i][n]+query(i-k,j-k,i,j));
				suf[i-k]=max(suf[i-k],s[n][n]-s[i-k-1][n]+query(i-k,j-k,i,j));
			}
		}
	for (int i=1;i<=n;i++) pre[i]=max(pre[i],pre[i-1]+s[i][n]-s[i-1][n]);
	for (int i=n;i>=1;i--) suf[i]=max(suf[i],suf[i+1]+s[i][n]-s[i-1][n]);
	for (int i=0;i<=n;i++)
	{
		ans=max(ans,pre[i]+suf[i+1]);
		// cout<<i<<" "<<pre[i]<<" "<<suf[i+1]<<endl;
		
	}
	//OO


	for (int x=1;x<=n;x++)
	{
		for (int y=0;y<=n+1;y++)
				for (int i=0;i<=n+1;i++)
					for (int j=0;j<=n+1;j++) F[y][i][j]=-inf;
		for (int i=x;i<=n;i++)
			for (int j=1;j<=n;j++)
				for (int k=0;k<min(i,j);k++)
					if (i-k<=x)
					{
						F[j-k][i][j]=max(F[j-k][i][j],query(i-k,j-k,i,j));
					}
		for (int y=1;y<=n;y++)
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++)
					F[y][i][j]=max(F[y-1][i][j],F[y][i][j]);
		for (int y=1;y<=n;y++)
			for (int i=n;i>=1;i--)
				for (int j=n;j>=1;j--)
					F[y][i][j]=max({F[y][i][j],F[y][i][j+1],F[y][i+1][j]});
		for (int y=1;y<=n;y++)
			for (int X=x;X<=n;X++)
				for (int Y=y;Y<=n;Y++)
				if (X-x==Y-y)
				{
					ans=max(ans,s[n][n]+F[y][X][Y]-query(x,y,X,Y));
				}
	}
	// cout<<"??"<<ans<<endl;
	
	cout<<ans<<'\n';
			

						
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5996kb

input:

400000 400000
1 2 1 4 1 1 5 4 6 5 9 1 1 13 3 8 12 16 3 11 8 8 2 18 21 15 7 23 11 6 4 26 17 5 12 6 5 28 32 26 21 5 19 1 25 25 11 26 47 11 31 25 18 7 25 36 40 23 54 31 14 62 61 33 57 40 11 16 24 51 69 25 55 51 55 65 34 19 18 21 20 62 64 83 22 48 67 47 21 27 30 63 10 14 70 63 18 17 74 98 40 89 10 7 30 ...

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-03 22:26:45 | OpenSource Project