Advertisement
Dang_Quan_10_Tin

PATH

Jun 25th, 2022
616
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define task "PATH"
  5. #define pll pair<ll, ll>
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. using namespace std;
  10. const int mod = 998244353;
  11. const int N = 1e2+5;
  12. const int M = 1e3+5;
  13. const ll base = 257;
  14. const ll base1 = 311;
  15. int n, m, a[M][M], k, res;
  16. vector<int> adj[N];
  17. char c[M][M];
  18. ll dp[N][N][N][N], ans, f[M][M];
  19. int posy(int x, int k, bool down)
  20. {
  21.     if(down)return k-(x-1);
  22.     k = (m+n-1)/2-k+1;
  23.     return m-(k-1-(n-x));
  24. }
  25. void add(ll& x, ll y)
  26. {
  27.     if(x < y)x = y;
  28. }
  29. void add(int step, int lst, int lx, int ly, int rx, int ry, ll v)
  30. {
  31.     if(c[lx][ly] == c[rx][ry])
  32.         add(dp[step][lx][rx][lst], v+a[lx][ly]+a[rx][ry]);
  33. }
  34. void sol(int itest)
  35. {
  36.     cin >> n >> m;
  37.     for(int i = 1; i <= n; i ++)
  38.         for(int j = 1; j <= m; j ++)cin >> c[i][j];
  39.     for(int i = 1; i <= n; i ++)
  40.         for(int j = 1; j <= m; j ++)cin >> a[i][j];
  41.     if(max(n, m) > 100)
  42.     {
  43.         for(int i = 1; i <= n; i ++)
  44.         {
  45.             for(int j = 1; j <= m; j ++)
  46.             {
  47.                 f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
  48.             }
  49.         }
  50.         cout << f[n][m];
  51.         return;
  52.     }
  53.     memset(dp, -1, sizeof(dp));
  54.     for(int x = 1; x <= n; x ++)
  55.     {
  56.         int y = posy(x, 1, 0);
  57.         if(1 > y || y > m)continue;
  58.         if(c[1][1] == c[x][y])
  59.             add(dp[1][1][x][x], a[1][1]+a[x][y]);
  60.     }
  61.     ans = -1;
  62.     for(int step = 1; step < (n+m-1)/2; step ++)
  63.     {
  64.         for(int lx = 1; lx <= n; lx ++)
  65.         {
  66.             for(int lst = lx; lst <= n; lst ++)
  67.             {
  68.                 for(int rx = lst; rx <= n; rx ++)
  69.                 {
  70.                     if(dp[step][lx][rx][lst] == -1)continue;
  71.                     int ly = posy(lx, step, 1), ry = posy(rx, step, 0);
  72.                     if(min(ly, ry) < 1 || max(ly, ry) > m)continue;
  73.                     for(int x1 = lx; x1 <= min(lx+1, lst); x1 ++)
  74.                     {
  75.                         for(int x2 = rx; x2 <= min(rx+1, n); x2 ++)
  76.                         {
  77.                             int y1 = posy(x1, step+1, 1);
  78.                             int y2 = posy(x2, step+1, 0);
  79.                             if(min(y1, y2) < 1 || max(y1, y2) > m)continue;
  80.                             add(step+1, lst, x1, y1, x2, y2, dp[step][lx][rx][lst]);
  81.                         }
  82.                     }
  83.                 }
  84.             }
  85.  
  86.         }
  87.     }
  88.     for(int i = 1; i <= n; i ++)
  89.     {
  90.         ans = max(dp[(m+n-1)/2][i][n][i], ans);
  91.         ans = max(dp[(m+n-1)/2][i][n][i+1], ans);
  92.     }
  93.     cout << ans;
  94. }
  95. int main()
  96. {
  97.     if(fopen(task".inp", "r")){
  98.        freopen(task".inp", "r", stdin);
  99.        freopen(task".out", "w", stdout);
  100.     }
  101.     ios_base::sync_with_stdio(0);
  102.     cin.tie(0);
  103.     cout.tie(0);
  104.     int ntest;
  105.     ntest = 1;
  106.     //cin >> ntest;
  107.     for(int i = 1; i <= ntest; i ++)
  108.         sol(i);
  109. }
  110.  
Advertisement
RAW Paste Data Copied
Advertisement