能给代码看一下吗亲
by Lovely_Chtholly @ 2022-08-16 21:59:45
@[OIer_FY](/user/759370) 您是把SPJ交上去了吗
by Haber @ 2022-08-16 22:03:46
@[OIer_FY](/user/759370) 应该是 testlib 自带一个 `opt`，然后你重新定义了一个。
by m256i @ 2022-08-16 22:17:10
```c++
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2005;
ll s[N][N];
int d[N][N], l[N], r[N], st[N];
bool a[N][N];
ll area(int x1, int y1, int x2, int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
int main()
{
ll k;
int n;
freopen("kup.in","r",stdin);
freopen("kup.out","w",stdout);
scanf("%lld %d",&k,&n);
for (int i=1; i <= n; i++)
for (int j=1; j <= n; j++)
{
ll x;
scanf("%lld",&x);
if (x > 2*k) a[i][j] = true;
else if (k <= x && x <= 2*k)
{
printf("%d %d %d %d",i,j,i,j);
return 0;
}
s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
}
for (int j=1; j <= n; j++)
{
d[n+1][j] = n;
for (int i=n; i >= 1; i--)
{
if (a[i][j]) d[i][j] = i-1;
else d[i][j] = d[i+1][j];
}
}
int x1, y1, x2, y2, sum = 0;
for (int i=1; i <= n; i++)
{
for (int j=1; j <= n; j++) r[j] = n;
int top = 0;
for (int j=1; j <= n; j++)
{
while (top && d[i][j] < d[i][st[top]])
{
r[st[top]] = j-1;
top--;
}
st[++top] = j;
}
for (int j=1; j <= n; j++) l[j] = 1;
top = 0;
for (int j=n; j >= 1; j--)
{
while (top && d[i][j] < d[i][st[top]])
{
l[st[top]] = j+1;
top--;
}
st[++top] = j;
}
for (int j=1; j <= n; j++)
if (area(i,l[j],d[i][j],r[j]) > sum) x1 = i, y1 = l[j], x2 = d[i][j], y2 = r[j], sum = area(i,l[j],d[i][j],r[j]);
}
while (x1 < x2)
{
sum = area(x1,y1,x2,y2);
if (k <= sum && sum <= 2*k)
{
printf("%d %d %d %d",x1,y1,x2,y2);
return 0;
}
if (sum < k)
{
printf("0 0 0 0");
return 0;
}
if (area(x1,y1,x2-1,y2) < k) x1 = x2;
else x2--;
}
while (y1 < y2)
{
sum = area(x1,y1,x2,y2);
if (k <= sum && sum <= 2*k)
{
printf("%d %d %d %d",x1,y1,x2,y2);
return 0;
}
if (sum < k)
{
printf("0 0 0 0");
return 0;
}
if (area(x1,y1,x2,y2-1) < k) y1 = y2;
else y2--;
}
printf("0 0 0 0\n");
return 0;
}
```
by OIer_FY @ 2022-08-17 15:58:32