C++14(g++5.4) 解法, 执行用时: 640ms, 内存消耗: 31860K, 提交时间: 2019-12-28 15:40:44
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e3+5;
int n,k;
ll a[N][N];
ll cal(int x,int y,int d) {
return a[x][y]-a[x-d][y]-a[x][y-d]+a[x-d][y-d];
}
bool check(int x) {
for(int i=x;i<=n;i++) {
for(int j=x;j<=n;j++) {
if(cal(i,j,x)>=k) return true;
}
}
return false;
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
scanf("%lld",&a[i][j]);
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int L=1,R=n,ans=-1;
while(L<=R) {
int mid=(L+R)>>1;
if(check(mid)) R=mid-1,ans=mid;
else L=mid+1;
}
if(ans==-1) printf("I'm a Gold Chef!\n");
else printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 490ms, 内存消耗: 63080K, 提交时间: 2019-12-28 16:35:43
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1;
long long n,m,a[N][N],s[N][N],l,r;
bool C(int k)
{
for(int i=k;i<=n;i++)
for(int j=k;j<=n;j++)
if(s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k]>=m)
return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][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];
l=1,r=n;
while(l<r)
if(C((l+r)/2))
r=(l+r)/2;
else
l=(l+r)/2+1;
if(C(l))
cout<<l;
else
cout<<"I'm a Gold Chef!";
return 0;
}
)，k(
)，n代表HJGG提供的美食矩阵是一个n阶矩阵，k代表HiLin的饥饿度，接下来有n行输入，每一行输入n个整数x（
），代表着在位置的美食能为HiLin消除的饥饿度。