QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413607 | #6846. Wiring Engineering | Bronya | WA | 24ms | 11972kb | C++14 | 3.8kb | 2024-05-17 19:56:39 | 2024-05-17 19:56:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[2][505],b[2][505];
int w[2][505][505];
struct query{
int l,r,L,R;
}Q[300005];
long long ans[300005];
long long f[505][505][2][2],dp[505][505];
long long sav[505];
void Solve(int l,int r,int L,int R,vector<int>&vt,int op){
if(vt.empty())return;
// cerr<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
if(l==r){
for(auto x:vt){
long long sum=-a[0][l];
for(int i=Q[x].L;i<=Q[x].R;i++)sum+=max(0,-b[0][i]+w[0][l][i]);
ans[x]=max(sum,0ll);
}
return;
}
if(op){
swap(l,r);swap(L,R);
for(auto x:vt)
swap(Q[x].l,Q[x].L),swap(Q[x].r,Q[x].R);
}
int mid=l+r>>1;
vector<int>vm,vl,vr;
for(auto x:vt)
if(Q[x].l<=mid&&Q[x].r>mid)vm.push_back(x);
else if(Q[x].r<=mid)vl.push_back(x);
else vr.push_back(x);
if(!vm.empty()){
for(int m=L;m<=R;m++){
for(int s=0;s<2;s++){
for(int i=l;i<=r;i++)
for(int j=L;j<=R;j++)
for(int u=0;u<2;u++)
for(int v=0;v<2;v++)
f[i][j][u][v]=-1e18;
for(auto x:vm)sav[x]=(s?-b[op][m]:0);
f[mid][m][0][s]=0;
for(int i=mid;i>=l;i--)
for(int j=m;j>=L;j--){
dp[i][j]=-1e18;
for(int u=0;u<2;u++)
for(int v=0;v<2;v++){
dp[i][j]=max(dp[i][j],f[i][j][u][v]);
if(!u||!v)f[i][j][1][1]=max(f[i][j][1][1],f[i][j][u][v]+w[op][i][j]-(u?0:a[op][i])-(v?0:b[op][j]));
f[i-1][j][0][v]=max(f[i-1][j][0][v],f[i][j][u][v]);
f[i][j-1][u][0]=max(f[i][j-1][u][0],f[i][j][u][v]);
}
}
for(auto x:vm)
if(Q[x].L<=m&&Q[x].R>=m)sav[x]+=dp[Q[x].l][Q[x].L];
f[mid+1][m][0][s]=0;
for(int i=mid+1;i<=r;i++)
for(int j=m;j<=R;j++){
dp[i][j]=-1e18;
for(int u=0;u<2;u++)
for(int v=0;v<2;v++){
dp[i][j]=max(dp[i][j],f[i][j][u][v]);
if(!u||!v)f[i][j][1][1]=max(f[i][j][1][1],f[i][j][u][v]+w[op][i][j]-(u?0:a[op][i])-(v?0:b[op][j]));
f[i+1][j][0][v]=max(f[i+1][j][0][v],f[i][j][u][v]);
f[i][j+1][u][0]=max(f[i][j+1][u][0],f[i][j][u][v]);
}
}
for(auto x:vm)
if(Q[x].L<=m&&Q[x].R>=m)sav[x]+=dp[Q[x].r][Q[x].R];
for(auto x:vm)ans[x]=max(ans[x],sav[x]);
}
}
}
if(op){
swap(l,r);swap(L,R);
for(auto x:vl)
swap(Q[x].l,Q[x].L),swap(Q[x].r,Q[x].R);
for(auto x:vr)
swap(Q[x].l,Q[x].L),swap(Q[x].r,Q[x].R);
Solve(l,r,L,mid,vl,op^1);
Solve(l,r,mid+1,R,vr,op^1);
}
else {
Solve(l,mid,L,R,vl,op^1);
Solve(mid+1,r,L,R,vr,op^1);
}
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[0][i]),b[1][i]=a[0][i];
for(int i=1;i<=n;i++)scanf("%d",&b[0][i]),a[1][i]=a[0][i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&w[0][i][j]),w[1][j][i]=w[0][i][j];
vector<int>vt;
for(int i=1;i<=q;i++){
scanf("%d%d%d%d",&Q[i].l,&Q[i].r,&Q[i].L,&Q[i].R);
vt.push_back(i);
}
Solve(1,n,1,n,vt,0);
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9944kb
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: 24ms
memory: 11972kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3201 5940 5940 9913 9913 9913 9913 9913 ...
result:
wrong answer 7th lines differ - expected: '734', found: '0'