QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165915#6846. Wiring Engineeringjiangly (Lingyu Jiang)WA 29ms6076kbC++208.8kb2023-09-05 22:59:332023-09-05 22:59:34

Judging History

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

  • [2023-09-05 22:59:34]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:6076kb
  • [2023-09-05 22:59:33]
  • 提交

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;
            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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

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: 29ms
memory: 6076kb

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:

wrong answer 1507th lines differ - expected: '21592', found: '18142'