RT,样例在跑的时候前两行还正常第三行突然跑到4100了。。。交上去竟然还A了5个点,想知道哪里有问题
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define INF 0x3f3f3f3f
#define get_max(x , y) \
{ \
x = max(x , y); \
}
#define int long long
inline int oqs(int x , int y){
return x << (y << 1);
}
const int kato = 100 + 10;
int n , m , val[kato][kato];
unordered_map<int , LL> dp[2];
inline LL DP(){
int tmp = (1 << ((m + 1) << 1)) - 1;
LL numnow = 0 , numnxt = 1 , ans = -INF;
dp[numnow][0] = 0;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
// cout << "QAQ" << '\n';
int S = k -> first; LL last = k -> second;
LL now = last + val[i][j];
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!L && !R){
if(j < m) get_max(dp[numnxt][S ^ oqs(1 , j - 1)^ oqs(2 , j)] , now);
get_max(dp[numnxt][S] , last);
}
if(L && !R){
if(i < n) get_max(dp[numnxt][S] , now);
if(j < m) get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(L , j)] , now);
}
if(!L && R){
if(i < n) get_max(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , now);
if(j < m) get_max(dp[numnxt][S] , now);
}
if(L == R){
if(L == 1 && R == 1){
int nowar = 0;
for(int p = j ; ; p ++){
int dou = (S >> (p << 1)) & 3;
if(dou == 1) nowar ++;
if(dou == 2) nowar --;
if(nowar == 0){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(2 , p) ^ oqs(1 , p)] , now);
break;
}
}
}
if(L == 2 && R == 2){
int nowar = 0;
for(int p = j - 1; ; p --){
int dou = (S >> (p << 1)) & 3;
if(dou == 2) nowar ++;
if(dou == 1) nowar --;
if(nowar == 0){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(1 , p) ^ oqs(2 , p)] , now);
break;
}
}
}
}
if(L == 2 && R == 1){
get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , now);
}
if(L == 1 && R == 2 && (S ^ oqs(L , j - 1) ^ oqs(R , j)) == 0){ ans = max(ans , now); }
}
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
dp[numnxt][(k -> first << 2) & tmp] += k -> second;
}
swap(numnxt , numnow);
// cout << ans << '\n';
}
return ans;
}
inline int Ame_(){
mian(n) , mian(m);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
mian(val[i][j]);
}
}
printf("%lld\n" , DP());
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
/*
4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000
*/