QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385914#6846. Wiring EngineeringTx_LcyRE 233ms92732kbC++144.7kb2024-04-11 09:58:002024-04-11 09:58:01

Judging History

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

  • [2024-04-11 09:58:01]
  • 评测
  • 测评结果:RE
  • 用时:233ms
  • 内存:92732kb
  • [2024-04-11 09:58:00]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define chkmax(x,y) (x=max(x,y))
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=105;
int const M=1e6+10;
int n,q,u[N],v[N],w[N][N],a[M],b[M],c[M],d[M],ans[M];
int dp1[N][N][N][2][2],dp2[N][N][N][2][2];
inline void work(int l,int r,int x,int y,vector<int>id){
    if (l>r || x>y || !id.size()) return;
    // if (r-l+1>=y-x+1){
        int md=(l+r)>>1;
        vector<int>L,R,M;
        for (auto i:id)
            if (b[i]<md) L.push_back(i);
            else if (a[i]>md) R.push_back(i);
            else M.push_back(i);
        // cerr<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<M.size()<<" nw\n";
        rep(tp,0,1){
            //tp -> [l,md-1] 与 [md,r] 选择区间是否有交
            //[md,i]
            memset(dp1,-0x3f,sizeof(dp1));
            rep(L,x,y) dp1[md-1][L][L-1][0][0]=0;
            rep(i,md,r){
                rep(L,x,y) rep(R,L-1,y) rep(s,0,1) rep(t,0,1){
                    //加入一个 i,i 不与 R 匹配
                    chkmax(dp1[i][L][R][0][t],dp1[i-1][L][R][s][t]);
                    //加入一个 i,i 与 R 匹配
                    if (L<=R) chkmax(dp1[i][L][R][1][1],dp1[i-1][L][R][s][t]-u[i]-(!t)*v[R]+w[i][R]);
                    //加入一个 R,i 不与 R 匹配
                    if (L<=R){
                        if (L==R && tp);
                        else chkmax(dp1[i][L][R][s][0],dp1[i][L][R-1][s][t]);
                    }
                    //加入一个 R,i 与 R 匹配
                    if (L<=R) chkmax(dp1[i][L][R][1][1],dp1[i][L][R-1][s][t]-(!s)*u[i]-v[R]+w[i][R]);
                }
            }
            // rep(i,md,r)
                // rep(L,x,y) rep(R,L-1,y) rep(s,0,1) rep(t,0,1)
                    // if (dp1[i][L][R][s][t]>(-1e17))
                        // cerr<<i<<' '<<L<<' '<<R<<' '<<s<<' '<<t<<' '<<dp1[i][L][R][s][t]<<" error?\n";
            // exit(0);
            memset(dp2,-0x3f,sizeof(dp2));
            rep(L,x-1,y+1) dp2[md][L][L-1][0][0]=0;
            per(i,md-1,l){
                per(L,y+1,x) rep(R,L-1,y) rep(s,0,1) rep(t,0,1){
                    //加入一个 i,i 不与 L 匹配
                    chkmax(dp2[i][L][R][0][t],dp2[i+1][L][R][s][t]);
                    //加入一个 i,i 与 L 匹配
                    if (L<=R) chkmax(dp2[i][L][R][1][1],dp2[i+1][L][R][s][t]-u[i]-(!t)*v[L]+w[i][L]);
                    //加入一个 L,i 不与 L 匹配
                    if (L<=R){
                        if (L==R && tp);
                        else chkmax(dp2[i][L][R][s][0],dp2[i][L+1][R][s][t]);
                    }
                    //加入一个 L,i 与 L 匹配
                    if (L<=R) chkmax(dp2[i][L][R][1][1],dp2[i][L+1][R][s][t]-(!s)*u[i]-v[L]+w[i][L]);
                }
            }
            // rep(i,l,md-1)
                // rep(L,x,y+1) rep(R,L-1,y) rep(s,0,1) rep(t,0,1)
                    // if (dp2[i][L][R][s][t]>(-1e17))
                        // cerr<<i<<' '<<L<<' '<<R<<' '<<s<<' '<<t<<' '<<dp2[i][L][R][s][t]<<" error?\n";
            for (auto i:M){
                // cerr<<i<<' '<<md<<' '<<tp<<' '<<l<<','<<r<<' '<<x<<','<<y<<" sol?\n";
                rep(k,c[i],d[i]){
                    int lef=-1e18,rig=-1e18;
                    rep(s,0,1) rep(t,0,1){
                        lef=max(lef,dp2[a[i]][c[i]][k][s][t]),
                        rig=max(rig,dp1[b[i]][k][d[i]][s][t]);
                        // cerr<<a[i]<<' '<<c[i]<<','<<k-(!tp)<<' '<<s<<','<<t<<' '<<dp2[a[i]][c[i]][k-(!tp)][s][t]<<" left\n";
                        // cerr<<b[i]<<' '<<k<<','<<d[i]<<' '<<s<<','<<t<<' '<<dp1[b[i]][k][d[i]][s][t]<<" right\n";
                    }
                    if (!tp) lef=max(0ll,lef),rig=max(0ll,rig);
                    // cerr<<i<<' '<<k<<' '<<lef<<' '<<rig<<' '<<tp*v[k]<<" ohhhh\n";
                    ans[i]=max(ans[i],lef+rig+tp*v[k]);
                }
            }
            // exit(0);
        }
        work(l,md-1,x,y,L),work(md+1,r,x,y,R);
    // }
}
inline void solve(){
    cin>>n>>q;
    rep(i,1,n) cin>>u[i];
    rep(i,1,n) cin>>v[i];
    rep(i,1,n) rep(j,1,n) cin>>w[i][j];
    vector<int>id;
    rep(i,1,q) cin>>a[i]>>b[i]>>c[i]>>d[i],id.push_back(i);
    work(1,n,1,n,id);
    rep(i,1,q) cout<<ans[i]<<'\n';
}
signed main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 85836kb

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: 0
Accepted
time: 230ms
memory: 89424kb

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
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
10799
10799
14772
14772
14772
14772
14772
20708
24243
25895
27159
33403
33403
33403
33469
33469
0
0
0
0
402
7728
10467
10467
14440
14440
14440
14440
14440
20376
239...

result:

ok 90000 lines

Test #3:

score: 0
Accepted
time: 219ms
memory: 92368kb

input:

24 90000
2882 8334 4022 5376 8457 3340 867 899 1508 727 7364 623 6553 7553 7719 6763 7732 3004 5920 4146 6661 4104 6283 8972
4478 5974 4930 4992 3905 9280 5603 2194 7539 6619 5862 151 8423 5365 219 5041 7657 7324 5990 3400 8540 4062 4172 7347
8383 9811 9948 8647 930 20 3735 8411 4325 4279 8849 3616 ...

output:

1023
4860
9878
13533
13533
13533
13533
19750
19750
19750
22737
26202
26202
26202
30484
31526
31526
32471
32471
38273
38273
43569
48112
48112
955
5973
9628
9628
9628
9628
15845
15845
15845
18832
22297
22297
22297
26579
27621
27621
28566
28566
34368
34368
39664
44207
44207
2136
5791
5791
5791
5791
120...

result:

ok 90000 lines

Test #4:

score: 0
Accepted
time: 228ms
memory: 89400kb

input:

24 90000
5827 3068 5413 8083 80 9169 8321 3897 4658 7830 2340 8206 1214 6308 5129 1455 2916 1859 2482 5258 7060 9652 1082 800
8155 1732 6246 3960 245 1183 1414 1277 4968 8201 6267 1932 1361 6774 1087 2440 3409 5345 8071 3990 632 7664 4733 5294
1185 6622 9262 7354 2910 1548 9877 2515 9039 9202 2820 2...

output:

0
0
2079
5473
8138
8503
16966
18204
22275
23276
23276
24228
24464
25082
28124
34856
34856
36225
36225
36225
36225
36225
36225
40176
0
2079
5473
8138
8503
16966
18204
22275
23276
23276
24228
24464
25082
28124
34856
34856
36225
36225
36225
36225
36225
36225
40176
0
583
3248
3613
12076
13314
17385
1838...

result:

ok 90000 lines

Test #5:

score: 0
Accepted
time: 233ms
memory: 92412kb

input:

24 90000
228 448 373 1000 1000 49 571 217 799 531 838 609 889 615 683 578 956 218 842 100 180 312 835 691
803 486 792 277 841 190 476 794 717 234 109 947 795 631 353 1000 708 501 113 708 125 716 452 915
9676 6488 8908 3177 3346 767 6103 2588 9360 3035 1212 564 8822 4147 8260 8212 6538 6006 8716 5567...

output:

8645
14647
22763
25663
28168
28745
34372
36166
44809
47610
48713
48713
56740
60256
68163
75375
81205
86710
95313
100172
107154
115433
124423
126873
5774
13890
16790
19295
19872
25499
27293
35936
38737
39840
39840
47867
51383
59290
66502
72332
77837
86440
91299
98281
106560
115550
118000
7888
10788
1...

result:

ok 90000 lines

Test #6:

score: 0
Accepted
time: 222ms
memory: 92732kb

input:

24 90000
57 21 22 28 66 90 53 16 85 37 59 21 34 17 16 47 21 32 22 27 93 52 63 66
15 7 77 52 38 42 24 38 81 49 57 45 36 63 23 93 75 28 23 34 48 71 78 64
8367 4296 343 546 7650 5845 8498 5888 2483 9099 2698 5872 3982 1036 6415 4326 9263 7076 7818 7907 6825 3203 2048 5487
6642 3448 1683 9585 9322 1651 ...

output:

8295
12584
12850
13344
20956
26759
35233
41083
43485
52535
55176
61003
64949
65922
72314
76547
85735
92783
100578
108451
115228
118360
120330
125753
4232
4498
4992
12604
18407
26881
32731
35133
44183
46824
52651
56597
57570
63962
68195
77383
84431
92226
100099
106876
110008
111978
117401
209
703
831...

result:

ok 90000 lines

Test #7:

score: 0
Accepted
time: 226ms
memory: 92696kb

input:

24 90000
2 2 10 6 7 7 2 9 1 8 1 2 9 6 6 10 7 8 7 6 6 5 4 5
3 9 4 5 2 3 8 2 6 2 6 2 5 1 10 5 4 3 2 6 5 7 1 1
8155 8001 2384 8872 2623 129 2105 9830 6007 6485 9339 7456 6246 1156 2019 1875 8275 6950 7885 4501 114 1456 9206 5279
9157 6539 6206 9430 353 5870 4767 6957 6129 3742 9953 8631 9898 8230 9641 ...

output:

8150
16142
18522
27389
30010
30136
32233
42061
48062
54545
63878
71332
77573
78728
80737
82607
90878
97825
105708
110203
110312
111761
120966
126244
7990
10370
19237
21858
21984
24081
33909
39910
46393
55726
63180
69421
70576
72585
74455
82726
89673
97556
102051
102160
103609
112814
118092
2378
1124...

result:

ok 90000 lines

Test #8:

score: 0
Accepted
time: 224ms
memory: 92452kb

input:

24 90000
1571 8593 7110 9439 5693 6004 2083 6762 6156 1082 3311 4826 2735 1518 4964 1627 8600 5434 1698 2333 1492 1819 9208 2385
6759 1678 1244 3701 7214 7740 7859 2612 1754 3579 702 7842 7407 6886 5612 9788 3791 803 8242 9388 2543 588 2137 3026
14 563 354 730 30 468 695 422 800 230 867 880 753 350 ...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90000 lines

Test #9:

score: 0
Accepted
time: 230ms
memory: 90384kb

input:

24 90000
9515 4114 9111 3785 1401 5622 2365 4538 8244 4565 1230 4659 6600 3020 4874 9402 7318 2149 8497 8821 657 3842 5678 9041
9219 834 1567 7528 7313 4701 6148 825 1732 3368 6419 6495 891 3569 9742 3361 5403 8315 5596 1155 6579 3964 772 4468
92 61 97 17 83 25 29 92 14 37 15 32 50 54 9 41 59 14 100...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90000 lines

Test #10:

score: 0
Accepted
time: 232ms
memory: 90652kb

input:

24 90000
7875 1831 8812 3686 3105 6713 7181 2621 3079 6665 4084 8202 6751 7113 1494 1987 9855 2854 12 5890 9938 529 9565 9636
5255 6704 8421 6138 595 5015 838 4001 5426 5839 3906 5656 568 6666 1024 8857 8690 237 8891 6247 6726 3097 1844 6980
9 3 8 1 8 9 3 7 4 7 8 7 1 5 6 3 3 5 3 3 4 3 8 3
9 3 10 8 8...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90000 lines

Test #11:

score: -100
Runtime Error

input:

300 100000
5892 2941 7796 3824 7699 6234 1720 4553 2224 3340 9567 897 7270 8556 8074 3842 7509 6342 9185 3140 3418 9783 8997 2773 8953 3806 9039 5780 5753 2259 6707 3211 3341 9795 8101 486 449 2952 3278 5997 1371 7167 5793 6654 4562 8639 8974 3875 754 7239 5575 4763 7555 4170 306 613 61 5074 2372 45...

output:


result: