fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define name "domine"
  4. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  5. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  6. #define ll long long
  7. #define fi first
  8. #define se second
  9. #define ii pair <int, int>
  10. #define sz(a) a.size()
  11. #define pb push_back
  12. #define MASK(x) (1ll << x)
  13. #define bit(x, i) ((x >> i) & 1)
  14. #define popcount(x) __builtin_popcount(x)
  15. #define mingdu signed main()
  16.  
  17. using namespace std;
  18.  
  19. const ll mod = 1e9 + 7;
  20.  
  21. void add(ll& a, ll b) {
  22.     a += b;
  23.     if (a >= mod) a -= mod;
  24.     if (a < 0) a += mod;
  25. }
  26.  
  27. template<class X, class Y> void mx(X &x, const Y y) {if (y > x) x = y;}
  28. template<class X, class Y> void mn(X &x, const Y y) {if (y < x) x = y;}
  29.  
  30. const int N = 1e3 + 5;
  31. int a[N][6], r, c, k;
  32. ll s[N+2][MASK(4) + 5], dp[2][2005][MASK(4) + 5];
  33. bool ok[MASK(4)+5];
  34.  
  35. void nhap() {
  36.     cin >> r >> c >> k;
  37.     FOR(i, 1, r) FOR(j, 0, c - 1) cin >> a[i][j];
  38. }
  39.  
  40. void giai() {
  41.     FOR(i, 1, r) FOR(msk, 0, MASK(c) - 1){
  42.         s[i][msk] = 0;
  43.         FOR(j, 0, c - 1) if(bit(msk,j)) s[i][msk] += a[i][j];
  44.     }
  45.     FOR(msk, 0, MASK(c) - 1) s[r + 1][msk] = 0;
  46.  
  47.     memset(ok, 0, sizeof ok);
  48.     ok[0] = 1;
  49.     FOR(i, 0, c - 2) ok[MASK(i) | MASK(i+1)] = 1;
  50.     if(c == 4) ok[MASK(c) - 1] = 1;
  51.  
  52.     ll inf = -9e18;
  53.     FOR(t, 0, k) FOR(msk, 0, MASK(c) - 1) dp[0][t][msk] = inf;
  54.     dp[0][0][0] = 0;
  55.  
  56.     int all = MASK(c) - 1;
  57.     FOR(i, 0, r - 1) {
  58.         int cur = i & 1, nxt = 1 - cur;
  59.         FOR(t, 0, k) FOR(msk, 0, MASK(c) - 1) dp[nxt][t][msk] = inf;
  60.         FOR(t, 0, k) FOR(msk1, 0, MASK(c) - 1) {
  61.             if (dp[cur][t][msk1] == inf) continue;
  62.             FOR(msk2, 0, MASK(c) - 1) if (ok[msk2] && (msk2 & msk1) == 0) {
  63.                 int tmp = (MASK(c) - 1) & (~msk1) & (~msk2);
  64.                 int msk3 = tmp;
  65.  
  66.                 while (1) {
  67.                     int use = popcount(msk2) / 2 + popcount(msk3);
  68.                     if (t + use <= k) {
  69.                         ll delta = s[i + 1][msk2] + s[i + 1][msk3] + s[i + 2][msk3];
  70.                         mx(dp[nxt][t + use][msk3], dp[cur][t][msk1] + delta);
  71.                     }
  72.  
  73.                     if (msk3 == 0) break;
  74.                     msk3 = (msk3 - 1) & tmp;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.  
  80.     cout << dp[r & 1][k][0] << "\n";
  81. }
  82.  
  83. mingdu{
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0); cout.tie(0);
  86.  
  87.     if(fopen(name".inp","r")){
  88.         freopen(name".inp","r",stdin);
  89.         freopen(name".out","w",stdout);
  90.     }
  91.  
  92.     nhap();
  93.     giai();
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pu0BBf
language:
C++14 (clang 8.0)
created:
5 hours 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!