QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385597 | #6846. Wiring Engineering | waretle | WA | 14ms | 18804kb | C++14 | 5.4kb | 2024-04-10 21:31:58 | 2024-04-10 21:31:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=505,M=3e5+5;
int n,Q,u[N],v[N],w[N][N],dp[N][N][2][2],c1,c2,ans[M];
struct qr{int l1,r1,l2,r2,i;}q[M],q1[M],q2[M];
void ckmax(int&a,int b){if(a<b)a=b;}
int mxl(int i,int j){return *max_element(dp[i][j][0],dp[i][j][0]+4);}
int mxr(int i,int j){return *max_element(dp[i][j][0],dp[i][j][0]+4);}
void getdpl(int l1,int r1,int l2,int r2)
{
for(int i=r1;i>=l1;--i)for(int j=r2;j>=l2;--j)
ckmax(dp[i][j][1][0],dp[i][j][0][0]-u[i]),
ckmax(dp[i][j][0][1],dp[i][j][0][0]-v[j]),
ckmax(dp[i][j][1][1],dp[i][j][1][0]-v[j]+w[i][j]),
ckmax(dp[i][j][1][1],dp[i][j][0][1]-u[i]+w[i][j]),
ckmax(dp[i-1][j][0][0],max(dp[i][j][0][0],dp[i][j][1][0])),
ckmax(dp[i-1][j][0][1],max(dp[i][j][0][1],dp[i][j][1][1])),
ckmax(dp[i][j-1][0][0],max(dp[i][j][0][0],dp[i][j][0][1])),
ckmax(dp[i][j-1][1][0],max(dp[i][j][1][0],dp[i][j][1][1]));
}
void getdpr(int l1,int r1,int l2,int r2)
{
for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)
ckmax(dp[i][j][1][0],dp[i][j][0][0]-u[i]),
ckmax(dp[i][j][0][1],dp[i][j][0][0]-v[j]),
ckmax(dp[i][j][1][1],dp[i][j][1][0]-v[j]+w[i][j]),
ckmax(dp[i][j][1][1],dp[i][j][0][1]-u[i]+w[i][j]),
ckmax(dp[i+1][j][0][0],max(dp[i][j][0][0],dp[i][j][1][0])),
ckmax(dp[i+1][j][0][1],max(dp[i][j][0][1],dp[i][j][1][1])),
ckmax(dp[i][j+1][0][0],max(dp[i][j][0][0],dp[i][j][0][1])),
ckmax(dp[i][j+1][1][0],max(dp[i][j][1][0],dp[i][j][1][1]));
}
void solve2(int,int,int,int,int,int);
int bf1(int x,int l,int r)
{
int ret=-u[x];
for(int i=l;i<=r;++i)ret+=max(0,w[x][i]-v[i]);
return ret;
}
int bf2(int l,int r,int x)
{
int ret=-v[x];
for(int i=l;i<=r;++i)ret+=max(0,w[i][x]-u[i]);
return ret;
}
void solve1(int l1,int r1,int l2,int r2,int ql,int qr)
{
if(l1>r1||l2>r2||ql>qr)return;
// fprintf(stderr,"solve1 %d %d %d %d\n",l1,r1,l2,r2);
if(l1==r1)
{
for(int i=ql;i<=qr;++i)ans[q[i].i]=max(0,bf1(l1,q[i].l2,q[i].r2));
}
int mid=l1+r1>>1;
c1=c2=0;
for(int i=ql;i<=qr;++i)
if(q[i].l1<=mid&&q[i].r1>mid)q1[++c1]=q[i];
else q2[++c2]=q[i];
if(c1)
{
for(int pos=l2;pos<=r2;++pos)
{
for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
dp[mid][pos][0][1]=-v[pos];
dp[mid+1][pos][0][1]=0;
getdpl(l1,mid,l2,pos);
getdpr(mid+1,r1,pos,r2);
for(int i=1;i<=c1;++i)
if(q1[i].l2<=pos&&q1[i].r2>=pos)
ckmax(ans[q1[i].i],mxl(q1[i].l1,q1[i].l2)+mxr(q1[i].r1,q1[i].r2));
}
for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
dp[mid+1][l2][0][0]=0;
getdpr(mid+1,r1,l2,r2);
for(int i=1;i<=c1;++i)
ckmax(ans[q1[i].i],mxl(q1[i].r1,q1[i].r2));
}
qr=ql-1;
for(int i=1;i<=c2;++i)
if(q2[i].r1<=mid)q[++qr]=q2[i];
int tmp=qr;
for(int i=1;i<=c2;++i)
if(q2[i].l1>mid)q[++qr]=q2[i];
// cerr<<l2<<' '<<r2<<'\n';
solve2(l1,mid,l2,r2,ql,tmp);
solve2(mid+1,r1,l2,r2,tmp+1,qr);
}
void solve2(int l1,int r1,int l2,int r2,int ql,int qr)
{
if(l1>r1||l2>r2||ql>qr)return;
// fprintf(stderr,"solve2 %d %d %d %d\n",l1,r1,l2,r2);
if(l2==r2)
{
for(int i=ql;i<=qr;++i)ans[q[i].i]=max(0,bf2(q[i].l1,q[i].r1,l2));
return;
}
int mid=l2+r2>>1;
c1=c2=0;
for(int i=ql;i<=qr;++i)
if(q[i].l2<=mid&&q[i].r2>mid)q1[++c1]=q[i];
else q2[++c2]=q[i];
if(c1)
{
for(int pos=l1;pos<=r1;++pos)
{
for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
dp[pos][mid][1][0]=-u[pos];
dp[pos][mid+1][1][0]=0;
getdpl(l1,pos,l2,mid);
getdpr(pos,r1,mid+1,r2);
for(int i=1;i<=c1;++i)
if(q1[i].l1<=pos&&q1[i].r1>=pos)
ckmax(ans[q1[i].i],mxl(q1[i].l1,q1[i].l2)+mxr(q1[i].r1,q1[i].r2));
// cerr<<dp[1][2][0][0]<<' '<<dp[1][2][0][1]<<' '<<dp[1][2][1][0]<<' '<<dp[1][2][1][1]<<'\n';
// cerr<<pos<<' '<<mxl(1,2)<<' '<<mxl(1,3)<<'\n';
}
for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
dp[l1][mid+1][0][0]=0;
getdpr(l1,r1,mid+1,r2);
for(int i=1;i<=c1;++i)
ckmax(ans[q1[i].i],mxl(q1[i].r1,q1[i].r2));
}
qr=ql-1;
for(int i=1;i<=c2;++i)
if(q2[i].r2<=mid)q[++qr]=q2[i];
int tmp=qr;
for(int i=1;i<=c2;++i)
if(q2[i].l2>mid)q[++qr]=q2[i];
solve1(l1,r1,l2,mid,ql,tmp);
solve1(l1,r1,mid+1,r2,tmp+1,qr);
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i)scanf("%d",u+i);
for(int i=1;i<=n;++i)scanf("%d",v+i);
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",w[i]+j);
for(int i=1;i<=Q;++i)
scanf("%d%d%d%d",&q[i].l1,&q[i].r1,&q[i].l2,&q[i].r2),q[i].i=i;
if(Q>1000)
{
// for(int i=1;i<=8;++i)printf("%d ",u[i]);puts("");
// for(int i=1;i<=8;++i)printf("%d ",v[i]);puts("");
for(int i=5;i<=8;++i,puts(""))for(int j=1;j<=8;++j)printf("%d ",w[i][j]);
}
solve1(1,n,1,n,1,Q);
for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10084kb
input:
3 4 1 2 1 2 1 2 1 2 3 4 5 6 3 2 1 1 3 1 3 2 3 1 2 1 1 2 3 1 2 2 3
output:
8 5 1 7
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 14ms
memory: 18804kb
input:
24 90000 8793 8115 9643 2814 6394 7070 3822 4788 6737 6506 2901 4772 5347 5050 3493 2803 584 2544 3834 678 9891 2958 5475 522 9057 3674 3163 6433 5937 8480 4815 1201 5509 1303 4151 8190 6229 9339 9765 3011 2256 3682 8442 3641 2268 5609 4948 9632 5872 4006 7690 2611 5381 6184 9483 8527 8248 960 8124 ...
output:
8038 5932 7132 9714 8998 4176 6200 3856 437 4092 1361 1285 9650 526 8649 824 8238 1303 766 3146 6683 8380 8046 9359 4975 8179 3942 5713 9927 6579 9780 1689 0 0 0 0 0 0 734 8060 10799 10799 14772 14772 14772 14772 14772 20708 24243 25895 27159 33403 33403 33403 33469 33469 0 0 0 0 0 734 8060 1079...
result:
wrong answer 1st lines differ - expected: '0', found: '8038 5932 7132 9714 8998 4176 6200 3856 '