fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define B break
  5. #define C continue
  6. #define R return
  7. #define be(a) a.begin(),a.end()
  8. #define fast ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
  9. #define endl "\n"
  10. using namespace std;
  11. int T,_t=1,n,i,j,k,x,y,m,ans;
  12. int b[10][2],d[2002][2300],c[2002][2300],sum[2002][520],a[2002][10];
  13. vector<int>v[10];
  14. vector<pair<int,int> >nxt[10][3000];
  15. string s,t,bin[10][1000];
  16. vector<string>st[10];
  17. vector<int>ind[10];
  18. int mask,nofgrp,newmask;
  19. void gen(int i,string s){
  20.     int j;
  21.     if(i==m) {
  22.         int mask=0,nofgrp=1+(m+1)/2;
  23.         for(j=0;j<m;j++) {
  24.             mask=mask*nofgrp+s[j]-'0';
  25.         }
  26.         ind[m][mask]=v[m].size();
  27.         v[m].emplace_back(mask);
  28.         R ;
  29.     }
  30.     gen(i+1,s+'0');
  31.     if(i&&s[i-1]!='0')
  32.         gen(i+1,s+s[i-1]);
  33.     else {
  34.         int x=1;
  35.         for(j=0;j<i;j++)
  36.             x=max(x,s[j]-'0'+1);
  37.         for(x;x>0;x--)
  38.             gen(i+1,s+char('0'+x));
  39.     }
  40. }
  41. void dfs(int i,int j,int x){
  42.     if(i<0||i==m||b[i][j]!=-1) R ;
  43.     b[i][j]=x;
  44.     dfs(i,1^j,x);
  45.     dfs(i-1,j,x);
  46.     dfs(i+1,j,x);
  47.     if(j==0) {
  48.         for(int k=j+1;k<m;k++)
  49.             if(s[i]==s[k])
  50.                 dfs(k,j,x);
  51.     }
  52. }
  53. string getString(int mask,int m){
  54.     string s="";
  55.     int nofgrp=1+(m+1)/2;
  56.     for(int i=0;i<m;i++)
  57.         s+='0'+mask%nofgrp,
  58.         mask/=nofgrp;
  59.     reverse(be(s));
  60.     R s;
  61. }
  62. string getBin(int mask,int m){
  63.     string s="";
  64.     for(int i=0;i<m;i++)
  65.         if((1<<i)&mask) s+='1';
  66.         else s+='0';
  67.     reverse(be(s));
  68.     R s;
  69. }
  70. int dp(int i,int mask) {
  71.     string &s=st[m][mask];
  72.     if(i==n) {
  73.         for(int j=0;j<m;j++) {
  74.             if(s[j]>'1')
  75.                 R -1e9;
  76.         }
  77.         R 0;
  78.     }
  79.     int in=ind[m][mask];
  80.     int &ret=d[i][in];
  81.     if(c[i][in]==T) R ret;
  82.     c[i][in]=T;
  83.     ret=-1e9;
  84.     int j;
  85.     for(j=0;j<m;j++)
  86.         if(s[j]>'1')
  87.             B;
  88.     if(j==m)
  89.         ret=0;
  90.     for(auto it:nxt[m][in]){
  91.         ret=max(ret,sum[i][it.F]+dp(i+1,it.S));
  92.     }
  93.     R ret;
  94. }
  95. int ff(){
  96.     k=-1e9;
  97.     cin>>n>>m;
  98.     for(i=0;i<n;i++) {
  99.         for(j=0;j<m;j++) {
  100.             cin>>a[i][j];
  101.             k=max(k,a[i][j]);
  102.         }
  103.     }
  104.     if(k<0) R cout<<k,0;
  105.     for(i=0;i<n;i++) {
  106.         for(mask=0;mask<(1<<m);mask++) {
  107.             x=0;
  108.             for(j=0;j<m;j++)
  109.                 if((1<<j)&mask)
  110.                     x+=a[i][m-1-j];
  111.             sum[i][mask]=x;
  112.         }
  113.     }
  114.     ans=dp(0,0);
  115.     cout<<ans;
  116.     R 0;
  117. }
  118. int main()
  119. {
  120.     fast
  121.     ///resize
  122.     for(m=1;m<=9;m++){
  123.         x=1;
  124.         y=1+(m+1)/2;
  125.         for(i=1;i<=m;i++){
  126.             x*=y;
  127.         }
  128.         st[m] .resize(x);
  129.         ind[m].resize(x);
  130.     }
  131.     ///resize done
  132.     ///generate masks
  133.     for(m=1;m<=9;m++){
  134.         gen(0,"");
  135.     }
  136.     ///done
  137.     ///store strings
  138.     for(m=1;m<=9;m++){
  139.         for(auto mask1:v[m]){
  140.             st[m][mask1]=getString(mask1,m);
  141.         }
  142.         for(mask=0;mask<(1<<m);mask++) {
  143.             bin[m][mask]=getBin(mask,m);
  144.         }
  145.     }
  146.     ///store done
  147.     ///find next mask
  148.     for(m=1;m<=9;m++) {
  149.         for(auto mask1:v[m]){
  150.             s=st[m][mask1];
  151.             for(mask=0;mask<(1<<m);mask++) {
  152.                 ///check
  153.                 string &t=bin[m][mask];
  154.                 for(i=0;i<=m;i++) b[i][0]=0;
  155.                 for(i=0;i<m;i++)
  156.                     if(t[i]=='1')
  157.                         b[s[i]-'0'][0]=1;
  158.                 for(i=0;i<m;i++)
  159.                     if(s[i]!='0'&&b[s[i]-'0'][0]==0)
  160.                         B;
  161.                 if(i!=m)
  162.                     C;
  163.                 ///check done
  164.                 ///memset
  165.                 for(i=0;i<m;i++){
  166.                     if(s[i]=='0') b[i][0]=0;
  167.                     else          b[i][0]=-1;
  168.                     if(t[i]=='0') b[i][1]=0;
  169.                     else          b[i][1]=-1;
  170.                 }
  171.                 ///memset done
  172.                 ///dfs
  173.                 x=0;
  174.                 for(i=0;i<m;i++){
  175.                     if(t[i]=='1'&&b[i][1]==-1){
  176.                         x++;
  177.                         dfs(i,1,x);
  178.                     }
  179.                 }
  180.                 ///dfs done
  181.                 ///store
  182.                 nofgrp=1+(m+1)/2,newmask=0;
  183.                 for(i=0;i<m;i++)
  184.                     newmask=newmask*nofgrp+b[i][1];
  185.                 j=ind[m][mask1];
  186.                 nxt[m][j].emplace_back(make_pair(mask,newmask));
  187.             }
  188.         }
  189.     }
  190.     cin>>_t;
  191.     for(T=1;T<=_t;T++){
  192.         ff();
  193.         cout<<endl;
  194.     }
  195.     R 0;
  196. }
  197.  
Success #stdin #stdout 0.38s 382648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1000000000
https://ideone.com/sgatnI
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!