QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385592#6846. Wiring EngineeringwaretleWA 17ms16896kbC++145.4kb2024-04-10 21:30:392024-04-10 21:30:40

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 21:30:40]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:16896kb
  • [2024-04-10 21:30:39]
  • 提交

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=1;i<=8;++i,puts(""))for(int j=1;j<=n;++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]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12116kb

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: 17ms
memory: 16896kb

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:

8793 8115 9643 2814 6394 7070 3822 4788 
9057 3674 3163 6433 5937 8480 4815 1201 
5872 4006 7690 2611 5381 6184 9483 8527 8248 960 8124 4978 2867 6549 3480 8947 5791 5334 9706 9885 5 2336 5014 2481 
5812 8807 9200 6534 6956 8961 9269 6995 3415 8825 8056 2729 5928 3992 2938 8122 4280 2619 6941 3707 7...

result:

wrong answer 1st lines differ - expected: '0', found: '8793 8115 9643 2814 6394 7070 3822 4788 '