比赛 |
2024暑假C班集训C |
评测结果 |
WWWTTTTTTTTTTTTTTTTW |
题目名称 |
洛希的极限 |
最终得分 |
0 |
用户昵称 |
djyqjy |
运行时间 |
79.985 s |
代码语言 |
C++ |
内存使用 |
3.48 MiB |
提交时间 |
2024-07-12 11:17:22 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2010,Q=500010;
const long long MOD=1e9+7;
struct rec
{
int x1,x2,y1,y2;
}rs[Q];
int n,m,q;
int t;
pair<int,long long> dp[N][N];
bool pan(int x,int y,int xx,int yy)
{
for(int i=1;i<=q;i++)
{
if(rs[i].x1<=x&&x<=rs[i].x2&&rs[i].y1<=y&&y<=rs[i].y2&&rs[i].x1<=xx&&xx<=rs[i].x2&&
rs[i].y1<=yy&&yy<=rs[i].y2) return 1;
}
return 0;
}
void dfs(int x,int y,int d,long long f)
{
bool flag=0;
if(dp[x][y].first)
{
if(dp[x][y].first>d) return;
if(dp[x][y].first==d) dp[x][y].second=(dp[x][y].second+f)%MOD,flag=1;
}
if(!flag) dp[x][y]=make_pair(d,f);
for(int xx=x+1;xx<=n;xx++)
{
for(int yy=y+1;yy<=m;yy++)
{
if(pan(x,y,xx,yy))
{
dfs(xx,yy,dp[x][y].first+1,dp[x][y].second);
}
}
}
return;
}
long long ansd,ansf;
int main()
{
freopen("roche.in","r",stdin);
freopen("roche.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&rs[i].x1,&rs[i].y1,&rs[i].x2,&rs[i].y2);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(dp[i][j].first!=0) continue;
dfs(i,j,1,1);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ansd<dp[i][j].first) ansd=dp[i][j].first,ansf=dp[i][j].second;
else if(ansd==dp[i][j].first) ansf=(ansf+dp[i][j].second)%MOD;
dp[i][j].first=0;
}
}
printf("%lld %lld\n",ansd,ansf);
ansd=ansf=0;
}
return 0;
}