\u5728\u4e00\u4e2a N*M \u7684\u77e9\u9635\u4e2d\u5bfb\u627e\u4e00\u4e2a A*B \u7684\u5b50\u77e9\u9635\uff0c\u5728\u8fd9\u4e2a A*B \u9636\u7684\u77e9\u9635\u4e2d\u518d\u5bfb\u627e\u4e00\u4e2a C*D \u7684\u5b50\u77e9\u9635\uff0c
\n\u4f7f\u5f97\u8fd9\u4e24\u4e2a\u77e9\u9635\u7684\u5dee\u6700\u5927\uff0c\u53e6\u3001C*D \u5b50\u77e9\u9635\u4e0d\u53ef\u4ee5\u89e6\u78b0 A*B \u77e9\u9635\u7684\u8fb9\u754c\u3002
\n( .. N \u2264 1000 \u2026 \uff09<\/p>\n
<\/p>\n
\u679a\u4e3e\u4e00\u9636\u5b50\u77e9\u9635\uff0c\u5bf9\u4e8c\u9636\u5b50\u77e9\u9635\u548c\u6bcf\u5217\uff0c\u5206\u522b\u7ef4\u62a4\u5355\u8c03\u961f\u5217\uff0c\u65f6\u95f4\u590d\u6742\u5ea6 O(NM)\u3002<\/p>\n
\r\n\r\nconst int N = 1001;\r\n\r\nstruct MonoList{\r\n int a[N], b[N];\r\n int op, cz, nn;\r\n inline int size(){\r\n return op - cz + 1;\r\n }\r\n inline int front(){\r\n return a[cz];\r\n }\r\n void init(){\r\n a[0] = 0, op = -1, cz = 0;\r\n }\r\n void init(int l){\r\n a[0] = 0, op = -1, cz = 0, nn = l;\r\n }\r\n\r\n void push_without_pop(int val, int label){\r\n while (op >= cz && val <= a[op]){\r\n --op;\r\n }\r\n a[++op] = val, b[op] = label;\r\n }\r\n\r\n void push(int val, int label){\r\n push_without_pop(val, label);\r\n if (b[cz] + nn == b[op]) ++cz;\r\n }\r\n\r\n} Sub, Col[N];\r\n\r\nint _T[101], s[N][N], ans;\r\nint n0, m0, n1, m1, n2, m2;\r\n\r\ninline int s1(int x, int y){\r\n return s[x][y] - s[x-n1][y] - s[x][y-m1] + s[x-n1][y-m1];\r\n}\r\n\r\ninline int s2(int x, int y){\r\n return s[x][y] - s[x-n2][y] - s[x][y-m2] + s[x-n2][y-m2];\r\n}\r\n\r\nint main(){\r\n\r\n REP_1(i, 100) _T[i] = (i * 71 + 17) % 100 + 1; Rush{\r\n\r\n RD(n0, m0, n1, m1, n2, m2);\r\n\r\n REP_1(i, n0) {\r\n int t; RD(t), s[i][1] = s[i-1][1] + t;\r\n FOR_1(j, 2, m0){\r\n t = _T[t];\r\n s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + t;\r\n }\r\n }\r\n\r\n ans = 0; FOR(j, m2+1, m0) Col[j].init(n1 - n2 - 1);\r\n Sub.init(m1 - m2 - 1);\r\n\r\n FOR(i, n2+1, n1-1) FOR(j, m2+1, m0)\r\n Col[j].push_without_pop(s2(i, j), i);\r\n\r\n FOR_1(i, n1, n0){\r\n\r\n FOR(j, m2+1, m0) Col[j].push(s2(i-1, j), i-1);\r\n\r\n Sub.init(); FOR(j, m2+1, m1) Sub.push_without_pop(Col[j].front(), j);\r\n FOR(j, m1, m0) {\r\n checkMax(ans, s1(i, j) - Sub.front());\r\n Sub.push(Col[j].front(), j);\r\n }\r\n\r\n checkMax(ans, s1(i, m0) - Sub.front());\r\n }\r\n\r\n OT(ans);\r\n }\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n