include<bits/stdc++.h>
define ll long long int
using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\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 <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
ll T,n,m,c;
ll a[N][N];
ll dp[N][N];
void init()
{
scanf("%I64d%I64d%I64d",&n,&m,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%I64d",&a[i][j]);
}
void DP()
{
for(int i=1;i<=n;i++)
{
ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
}
ll ans=-INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,dp[i][j]);
printf("%I64d\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)
{
init();
DP();
}
return 0;
}
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})$$$.
