QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #384735 | #6846. Wiring Engineering | yaoxi_std | TL | 0ms | 9744kb | C++14 | 10.3kb | 2024-04-10 11:33:53 | 2024-04-10 11:33:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 505, Q = 3e5 + 10;
int n, q, a[N], b[N], w[N][N], dpl[N][N][2][2][2][2], dpr[N][N][2][2][2][2], ans[Q];
vector<tuple<int, int, int, int, int>> qrya[N], qryb[N];
void solve(int la, int ra, int lb, int rb, bool typ) {
if (la > ra || lb > rb) return;
if (!typ) {
int mid = (la + ra) >> 1;
vector<tuple<int, int, int, int, int>> qry;
for (int i = la; i <= mid; ++i) {
for (auto it : qrya[i]) {
int qla, qra, qlb, qrb, id;
tie(qla, qra, qlb, qrb, id) = it;
if (mid <= qra && qra <= ra && lb <= qlb && qrb <= rb) qry.push_back(it);
}
}
for (int i = lb; i <= rb; ++i) {
memset(dpl[mid][i], -0x3f, sizeof(dpl[mid][i]));
dpl[mid][i][0][0][0][0] = 0;
dpl[mid][i][0][1][0][1] = -b[i];
dpl[mid][i][1][0][1][0] = -a[mid];
dpl[mid][i][1][1][1][1] = w[mid][i] - (a[mid] + b[i]);
for (int j = mid; j >= la; --j) {
for (int k = i; k >= lb; --k) {
if (j != mid || k != i) memset(dpl[j][k], -0x3f, sizeof(dpl[j][k]));
if (j < mid) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][0][y][p][q],
dpl[j + 1][k][x][y][p][q]);
chkmax(dpl[j][k][1][1][p][q],
dpl[j + 1][k][x][y][p][q] - a[j] - (!y ? b[k] : 0) + w[j][k]);
}
}
}
}
}
if (k < i) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][x][0][p][q],
dpl[j][k + 1][x][y][p][q]);
chkmax(dpl[j][k][1][1][p][q],
dpl[j][k + 1][x][y][p][q] - (!x ? a[j] : 0) - b[k] + w[j][k]);
}
}
}
}
}
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][0][0][p][q], dpl[j][k][x][y][p][q]);
}
}
}
}
}
}
memset(dpr[mid][i], -0x3f, sizeof(dpr[mid][i]));
dpr[mid][i][0][0][0][0] = 0;
dpr[mid][i][0][1][0][1] = -b[i];
dpr[mid][i][1][0][1][0] = -a[mid];
dpr[mid][i][1][1][1][1] = w[mid][i] - (a[mid] + b[i]);
for (int j = mid; j <= ra; ++j) {
for (int k = i; k <= rb; ++k) {
if (j != mid || k != i) memset(dpr[j][k], -0x3f, sizeof(dpr[j][k]));
if (j > mid) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][0][y][p][q],
dpr[j - 1][k][x][y][p][q]);
chkmax(dpr[j][k][1][1][p][q],
dpr[j - 1][k][x][y][p][q] - a[j] - (!y ? b[k] : 0) + w[j][k]);
}
}
}
}
}
if (k > i) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][x][0][p][q],
dpr[j][k - 1][x][y][p][q]);
chkmax(dpr[j][k][1][1][p][q],
dpr[j][k - 1][x][y][p][q] - (!x ? a[j] : 0) - b[k] + w[j][k]);
}
}
}
}
}
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][0][0][p][q], dpr[j][k][x][y][p][q]);
}
}
}
}
}
}
for (auto it : qry) {
int qla, qra, qlb, qrb, id;
tie(qla, qra, qlb, qrb, id) = it;
if (qlb <= i && i <= qrb) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
int val = dpl[qla][qlb][0][0][x][y] + dpr[qra][qrb][0][0][x][y];
if (x) val += a[mid];
if (y) val += b[i];
if (x && y) val -= w[mid][i];
chkmax(ans[id], val);
}
}
}
}
}
solve(la, mid - 1, lb, rb, !typ);
solve(mid + 1, ra, lb, rb, !typ);
} else {
int mid = (lb + rb) >> 1;
vector<tuple<int, int, int, int, int>> qry;
for (int i = lb; i <= mid; ++i) {
for (auto it : qryb[i]) {
int qla, qra, qlb, qrb, id;
tie(qla, qra, qlb, qrb, id) = it;
if (mid <= qrb && qrb <= rb && la <= qla && qra <= ra) qry.push_back(it);
}
}
for (int i = la; i <= ra; ++i) {
memset(dpl[i][mid], -0x3f, sizeof(dpl[i][mid]));
dpl[i][mid][0][0][0][0] = 0;
dpl[i][mid][0][1][0][1] = -b[mid];
dpl[i][mid][1][0][1][0] = -a[i];
dpl[i][mid][1][1][1][1] = w[i][mid] - (a[i] + b[mid]);
for (int j = i; j >= la; --j) {
for (int k = mid; k >= lb; --k) {
if (j != i && k != mid) memset(dpl[j][k], -0x3f, sizeof(dpl[j][k]));
if (j < i) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][0][y][p][q],
dpl[j + 1][k][x][y][p][q]);
chkmax(dpl[j][k][1][1][p][q],
dpl[j + 1][k][x][y][p][q] - a[j] - (!y ? b[k] : 0) + w[j][k]);
}
}
}
}
}
if (k < mid) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][x][0][p][q],
dpl[j][k + 1][x][y][p][q]);
chkmax(dpl[j][k][1][1][p][q],
dpl[j][k + 1][x][y][p][q] - (!x ? a[j] : 0) - b[k] + w[j][k]);
}
}
}
}
}
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpl[j][k][0][0][p][q], dpl[j][k][x][y][p][q]);
}
}
}
}
}
}
memset(dpr[i][mid], -0x3f, sizeof(dpr[i][mid]));
dpr[i][mid][0][0][0][0] = 0;
dpr[i][mid][0][1][0][1] = -b[mid];
dpr[i][mid][1][0][1][0] = -a[i];
dpr[i][mid][1][1][1][1] = w[i][mid] - (a[i] + b[mid]);
for (int j = i; j <= ra; ++j) {
for (int k = mid; k <= rb; ++k) {
if (j != i && k != mid) memset(dpr[j][k], -0x3f, sizeof(dpr[j][k]));
if (j > i) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][0][y][p][q],
dpr[j - 1][k][x][y][p][q]);
chkmax(dpr[j][k][1][1][p][q],
dpr[j - 1][k][x][y][p][q] - a[j] - (!y ? b[k] : 0) + w[j][k]);
}
}
}
}
}
if (k > mid) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][x][0][p][q],
dpr[j][k - 1][x][y][p][q]);
chkmax(dpr[j][k][1][1][p][q],
dpr[j][k - 1][x][y][p][q] - (!x ? a[j] : 0) - b[k] + w[j][k]);
}
}
}
}
}
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int p = 0; p < 2; ++p) {
for (int q = 0; q < 2; ++q) {
chkmax(dpr[j][k][0][0][p][q], dpr[j][k][x][y][p][q]);
}
}
}
}
}
}
for (auto it : qry) {
int qla, qra, qlb, qrb, id;
tie(qla, qra, qlb, qrb, id) = it;
if (qla <= i && i <= qra) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
int val = dpl[qla][qlb][0][0][x][y] + dpr[qra][qrb][0][0][x][y];
if (x) val += a[i];
if (y) val += b[mid];
if (x && y) val -= w[i][mid];
chkmax(ans[id], val);
}
}
}
}
}
solve(la, mid - 1, lb, rb, !typ);
solve(mid + 1, ra, lb, rb, !typ);
}
}
bool Med;
int main() {
// debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> w[i][j];
}
}
for (int i = 1, la, ra, lb, rb; i <= q; ++i) {
cin >> la >> ra >> lb >> rb;
qrya[la].push_back({la, ra, lb, rb, i});
qryb[lb].push_back({la, ra, lb, rb, i});
}
solve(1, n, 1, n, 0);
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
return 0;
}
/*
g++ -std=c++14 -O2 -o G G.cpp -Wall -Wextra
-Wshadow -fsanitize=address,undefined -g
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9744kb
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
Time Limit Exceeded
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 ...