QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #165919 | #6846. Wiring Engineering | ucup-team004 | TL | 57ms | 11220kb | C++20 | 8.8kb | 2023-09-05 23:02:40 | 2023-09-05 23:02:41 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int inf = 1E9;
void chmax(int &a, int b) {
if (a < b) {
a = b;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> u(n), v(n);
for (int i = 0; i < n; i++) {
std::cin >> u[i];
}
for (int i = 0; i < n; i++) {
std::cin >> v[i];
}
std::vector w(n, std::vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> w[i][j];
}
}
std::vector<int> a(q), b(q), c(q), d(q);
for (int i = 0; i < q; i++) {
std::cin >> a[i] >> b[i] >> c[i] >> d[i];
a[i]--, b[i]--, c[i]--, d[i]--;
}
std::vector dp(n, std::vector(n, std::array<std::array<int, 2>, 2>{}));
std::vector<int> ans(q);
auto solve = [&](auto self, int l1, int r1, int l2, int r2, const std::vector<int> qid) {
if (l1 > r1 || l2 > r2) {
return;
}
if (r1 - l1 > r2 - l2 || true) {
int m = (l1 + r1) / 2;
m = l1;
for (int y = l2; y <= r2; y++) {
for (int p1 = 0; p1 <= 1; p1++) {
for (int i = m; i >= l1; i--) {
for (int j = y; j >= l2; j--) {
dp[i][j] = {-inf, -inf, -inf, -inf};
}
}
for (int i = m; i <= r1; i++) {
for (int j = y; j <= r2; j++) {
dp[i][j] = {-inf, -inf, -inf, -inf};
}
}
dp[m][y][0][p1] = 0;
for (int i = m; i >= l1; i--) {
for (int j = y; j >= l2; j--) {
for (int o = 1; o >= 0; o--) {
for (int p = 1; p >= 0; p--) {
if (i < m) {
chmax(dp[i][j][o][p], dp[i + 1][j][0][p]);
}
if (j < y) {
chmax(dp[i][j][o][p], dp[i][j + 1][o][0]);
}
if (!o || !p) {
chmax(dp[i][j][o][p], dp[i][j][1][1] - (1 - o) * u[i] - (1 - p) * v[j] + w[i][j]);
}
}
}
}
}
for (int i = m; i <= r1; i++) {
for (int j = y; j <= r2; j++) {
for (int o = 0; o <= 1; o++) {
for (int p = 0; p <= 1; p++) {
if (i == m && j == m && p < p1) {
continue;
}
if (i < r1) {
chmax(dp[i + 1][j][0][p], dp[i][j][o][p]);
}
if (j < r2) {
chmax(dp[i][j + 1][o][0], dp[i][j][o][p]);
}
if (!o || !p) {
chmax(dp[i][j][1][1], dp[i][j][o][p] - (1 - o) * u[i] - (1 - p) * v[j] + w[i][j]);
}
}
}
}
}
for (auto i : qid) {
if (a[i] <= m && b[i] >= m && c[i] <= y && d[i] >= y) {
auto &dp2 = dp[b[i]][d[i]];
int mx2 = -inf;
for (int o = 0; o <= 1; o++) {
for (int p = 0; p <= 1; p++) {
if (b[i] == m && d[i] == y && p < p1) {
continue;
}
chmax(mx2, dp2[o][p]);
}
}
chmax(ans[i], dp[a[i]][c[i]][0][0] + mx2);
}
}
}
}
std::vector<int> q1, q2;
for (auto i : qid) {
if (b[i] < m) {
q1.push_back(i);
}
if (a[i] > m) {
q2.push_back(i);
}
}
self(self, l1, m - 1, l2, r2, q1);
self(self, m + 1, r1, l2, r2, q2);
} else {
int m = (l2 + r2) / 2;
for (int y = l1; y <= r1; y++) {
for (int p1 = 0; p1 <= 1; p1++) {
for (int i = m; i >= l2; i--) {
for (int j = y; j >= l1; j--) {
dp[i][j] = {-inf, -inf, -inf, -inf};
}
}
for (int i = m; i <= r2; i++) {
for (int j = y; j <= r1; j++) {
dp[i][j] = {-inf, -inf, -inf, -inf};
}
}
dp[m][y][0][p1] = 0;
for (int i = m; i >= l2; i--) {
for (int j = y; j >= l1; j--) {
for (int o = 1; o >= 0; o--) {
for (int p = 1; p >= 0; p--) {
if (i < m) {
chmax(dp[i][j][o][p], dp[i + 1][j][0][p]);
}
if (j < y) {
chmax(dp[i][j][o][p], dp[i][j + 1][o][0]);
}
if (!o || !p) {
chmax(dp[i][j][o][p], dp[i][j][1][1] - (1 - o) * v[i] - (1 - p) * u[j] + w[j][i]);
}
}
}
}
}
for (int i = m; i <= r2; i++) {
for (int j = y; j <= r1; j++) {
for (int o = 0; o <= 1; o++) {
for (int p = 0; p <= 1; p++) {
if (i == m && j == m && p < p1) {
continue;
}
if (i < r2) {
chmax(dp[i + 1][j][0][p], dp[i][j][o][p]);
}
if (j < r1) {
chmax(dp[i][j + 1][o][0], dp[i][j][o][p]);
}
if (!o || !p) {
chmax(dp[i][j][1][1], dp[i][j][o][p] - (1 - o) * v[i] - (1 - p) * u[j] + w[j][i]);
}
}
}
}
}
for (auto i : qid) {
if (a[i] <= y && b[i] >= y && c[i] <= m && d[i] >= m) {
auto &dp2 = dp[d[i]][b[i]];
int mx2 = -inf;
for (int o = 0; o <= 1; o++) {
for (int p = 0; p <= 1; p++) {
if (d[i] == m && b[i] == y && p < p1) {
continue;
}
chmax(mx2, dp2[o][p]);
}
}
chmax(ans[i], dp[c[i]][a[i]][0][0] + mx2);
}
}
}
}
std::vector<int> q1, q2;
for (auto i : qid) {
if (d[i] < m) {
q1.push_back(i);
}
if (c[i] > m) {
q2.push_back(i);
}
}
self(self, l1, r1, l2, m - 1, q1);
self(self, l1, r1, m + 1, r2, q2);
}
};
std::vector<int> qid(q);
std::iota(qid.begin(), qid.end(), 0);
solve(solve, 0, n - 1, 0, n - 1, qid);
for (int i = 0; i < q; i++) {
std::cout << ans[i] << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 55ms
memory: 11088kb
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: 57ms
memory: 11036kb
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: 51ms
memory: 11036kb
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: 43ms
memory: 11212kb
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: 44ms
memory: 11212kb
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: 51ms
memory: 11064kb
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: 45ms
memory: 11140kb
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: 52ms
memory: 11140kb
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: 54ms
memory: 11220kb
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
Time Limit Exceeded
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...