QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384737#6846. Wiring Engineeringyaoxi_stdWA 22ms17312kbC++1410.3kb2024-04-10 11:34:522024-04-10 11:34:54

Judging History

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

  • [2024-04-10 11:34:54]
  • 评测
  • 测评结果：WA
  • 用时：22ms
  • 内存：17312kb
查看
  • [2024-04-10 11:34:52]
  • 提交

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, ra, lb, mid - 1, !typ);
    solve(la, ra, mid + 1, 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
*/
源文件, 语言: C++14

詳細信息

Test #1:

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

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: 22ms
memory: 17312kb

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
4175
9926
9926
26331
34811
42137
44876
44876
48849
83659
92452
92452
92452
98388
101923
103575
104839
111083
111083
111083
111149
111149
0
4175
9926
9926
26331
34811
42137
44876
44876
48849
83659
92452
92452
92452
98388
101923
103575
104839
111083
111083
111083
111149
111149
0
0
0
21198
29678
37...

result:

wrong answer 3rd lines differ - expected: '0', found: '4175'
English 繁體中文 简体中文

伺服器時間: 2024-12-05 08:30:22 | 開源專案