If $$$n$$$ is a perfect square number, we find that the square dyeing scheme is always optimal.The answer is $$$4\sqrt{n}$$$.
Otherwise,if $$$n-\lfloor \sqrt{n} \rfloor ^2 \leq \lfloor \sqrt{n} \rfloor$$$,the answer is $$$4\lfloor \sqrt{n} \rfloor+2$$$.Otherwise the answer is $$$4\lfloor \sqrt{n} \rfloor+4$$$.
If $$$n$$$ is odd,we can traverse all cells, which is a simple situation.
If $$$n$$$ is even,we can skip one of $$$(1,2) (1,4) (1,6)...(1,n),(2,1),(2,3),(2,5)...(2,n-1)$$$.If there is a duplicate number, skip it. Otherwise, skip the maximum number.
First,be careful when $$$y=0$$$ and $$$k=1$$$ :)
Consider the answer with a length greater than $$$n$$$, which is always $$$10...01...1$$$.The construction is not hard.
What about the answer with length $$$n$$$?
Consider setting numbers from the highest bit to the lowest bit and current bit is $$$i$$$.If $$$y_i=1$$$,we must set $$$x_i=1$$$.Otherwise($$$y_i=0$$$),we either do set $$$x_i=0$$$ and go to the lower bit,or do set $$$x_i=1$$$, $$$x_{i+1}x_{i+2}...x_n=0...01...1$$$ and break.
For $$$y_i=0$$$,when can we do set $$$x_i=0$$$ and go to the lower bit?The condition is $$$re1>pre1_{i+1}$$$ or $$$re1==pre1_{i+1}$$$ and $$$pre1_{i+1}==tot1_{i+1}$$$.$$$re1$$$ is the current remaining number of $$$1's$$$,$$$pre1_{i+1}$$$ is the length of the continuous $$$1$$$ prefix of $$$y_{i+1}y_{i+2}...y_n$$$,and $$$tot1_{i+1}$$$ is the total of $$$1$$$ of $$$y_{i+1}y_{i+2}...y_n$$$.
Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.
It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.
Consider $$$b_i$$$,$$$k=max(j)(bit(b_i,j)=1)$$$.What about $$$b_{i+1}$$$?First,$$$bit_{j>k}(b_{i+1},j)=0$$$(otherwise,it contradicts the strict decrease of $$$b$$$).Then $$$bit(b_{i+1},k)$$$ must be $$$0$$$.Otherwise,we get $$$bit(a_i,k)!=bit(a_{i+1},k)$$$ and $$$bit(a_{i+1},k)!=bit(a_{i+2},k)$$$,which contradicts the strict increase of $$$a$$$.
Based on the above conclusion, we can make the optimal construction.
Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
for (cin >> t; t; t -= 1) {
int n, m;
i64 c;
cin >> n >> m >> c;
vector a(n, vector<i64>(m));
for (auto &ai : a) {
for (i64 &aij : ai) {
cin >> aij;
}
}
constexpr i64 df = -1e18;
i64 ans = df;
vector<i64> f(m, df);
for (auto &ai : a) {
for (int i = 0; i < m; i += 1) {
f[i] = max((i64)0, f[i] - c);
}
vector<i64> g(m, df);
{
vector<i64> p(m);
{
i64 mh = df, mg = df, sum = 0;
for (int i = 0; i < m; i += 1) {
mh = max(-sum + i * 2 * c, mh);
i64 hi = -i * 2 * c + mh;
mg = max(f[i] + hi + i * c, mg);
sum += ai[i];
p[i] += sum - i * c + mg;
}
}
{
i64 mg = df, sum = 0;
for (int i = m - 1; i >= 0; i -= 1) {
mg = max(mg, -sum - i * 2 * c);
p[i] += sum + i * 2 * c + mg;
sum += ai[i];
}
}
for (int i = 0; i < m; i += 1) {
g[i] = max(g[i], p[i]);
}
}
{
vector<i64> p(m);
{
i64 mh = df, mg = df, sum = 0;
for (int i = m - 1; i >= 0; i -= 1) {
mh = max(-sum - i * 2 * c, mh);
i64 hi = i * 2 * c + mh;
mg = max(f[i] + hi - i * c, mg);
sum += ai[i];
p[i] += sum + i * c + mg;
}
}
{
i64 mg = df, sum = 0;
for (int i = 0; i < m; i += 1) {
mg = max(mg, -sum + i * 2 * c);
p[i] += sum - i * 2 * c + mg;
sum += ai[i];
}
}
for (int i = 0; i < m; i += 1) {
g[i] = max(g[i], p[i]);
}
}
f.swap(g);
// for (i64 fi : f) {
// cout << fi << " ";
// }
// cout << "\n";
ans = max(ans, ranges::max(f));
}
cout << ans << "\n";
}
}
Consider DP.
Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.
Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.
Now consider which cell we go from to $$$(i,j)$$$.There are four situations.
$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;
$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;
$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;
$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.
$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.
$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.
