CF424D Biathlon Track 题解

题意

分析

真·暴力踩标算

记录从上至下、从下至上、从左至右、从右至左花费时间的前缀和，暴力枚举每一个左上角的点和右下角的点的坐标，计算出此时的总时间和 \(t\) 的差，如果比目前的最小值小就更新答案。时间复杂度大概为 \(O(\frac{n^2m^2}{4})\) ，显然会 TLE ，但是时限 4.5s ，随便卡卡就过了。

代码

#include 
#define int long long
using namespace std;
const int MAXN=307;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
	register T1 x=0;register bool f=false;char ch=getchar();
	while(ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch>='0') x=(x*10)+(ch^48),ch=getchar();
	x=(f?-x:x);a=x;qread(b...);
}
templateinline T qmax(const T &a,const T &b){return a>b?a:b;}
templateinline T qmin(const T &a,const T &b){return a=1;j--) pre[1][i][j]=pre[1][i][j+1]+f(i,j,i,j+1); // 从右往左
	for(j=1;j<=m;j++) for(i=1;i<=n;i++) pre[2][i][j]=pre[2][i-1][j]+f(i,j,i-1,j); // 从上往下
	for(j=1;j<=m;j++) for(i=n;i>=1;i--) pre[3][i][j]=pre[3][i+1][j]+f(i,j,i+1,j); // 从下往上
}
int mn=1e9+7,a1,b1,a2,b2;
signed main()
{
	qread(n,m,t,tp,tu,td);int i,j,k,l;
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) qread(a[i][j]);init();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			for(k=i+2;k<=n;k++)
			{
				for(l=j+2;l<=m;l++)
				{
					int tmp=pre[0][i][l]-pre[0][i][j]+ // 上面的一行
					        pre[1][k][j]-pre[1][k][l]+ // 下面的一行
							pre[2][k][l]-pre[2][i][l]+ // 右面的一列
							pre[3][i][j]-pre[3][k][j]; // 左面的一列
					tmp=abs(t-tmp);
					if(mn>=tmp)
					{
						mn=tmp;
						a1=i,b1=j,a2=k,b2=l;
					}
				}
			}
		}
	}
	printf("%lld %lld %lld %lld\n",a1,b1,a2,b2);
	return 0;
}