fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MOD 1000000007
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<ll, ll> ii;
  6. ll m, n, x, y, t, dem = 0, ma = -1, xma, yma, max_val = 0, max_val2, ans = 0;
  7. vector<ii> lon;
  8.  
  9. // ll mang[1005][1005];
  10.  
  11. int dx[] = {0, 0, 1, -1};
  12. int dy[] = {1, -1, 0, 0};
  13.  
  14. void solve()
  15. {
  16.     cin >> m >> n >> x >> y >> t;
  17.     ll mang[m + 1][n + 1];
  18.     // ll dp[m + 1][n + 1][t + 1];
  19.     for (ll i = 1; i <= m; i++)
  20.         for (ll j = 1; j <= n; j++)
  21.             cin >> mang[i][j];
  22.     // memset(dp, -1, sizeof(dp));
  23.     for (ll i = 1; i <= m; i++)
  24.         for (ll j = 1; j <= n; j++)
  25.         {
  26.             if (mang[i][j] == ma)
  27.                 lon.push_back(make_pair(i, j));
  28.             if (mang[i][j] > ma)
  29.             {
  30.                 ma = mang[i][j];
  31.                 lon.clear();
  32.                 lon.push_back(make_pair(i, j));
  33.             }
  34.         }
  35.  
  36.     // dp[x][y][0] = mang[x][y];
  37.     // for (ll k = 1; k <= t; k++)
  38.     // {
  39.     //     for (ll i = 1; i <= m; i++)
  40.     //         for (ll j = 1; j <= n; j++)
  41.     //         {
  42.     //             if (i > 1 && dp[i - 1][j][k - 1] != -1)
  43.     //                 dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + mang[i][j]);
  44.     //             if (j > 1 && dp[i][j - 1][k - 1] != -1)
  45.     //                 dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + mang[i][j]);
  46.     //             if (i < m && dp[i + 1][j][k - 1] != -1)
  47.     //                 dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k - 1] + mang[i][j]);
  48.     //             if (j < n && dp[i][j + 1][k - 1] != -1)
  49.     //                 dp[i][j][k] = max(dp[i][j][k], dp[i][j + 1][k - 1] + mang[i][j]);
  50.     //         }
  51.     // }
  52.  
  53.     // for (ll i = 1; i <= m; i++)
  54.     //     for (ll j = 1; j <= n; j++)
  55.     //         dem = max(dem, dp[i][j][t]);
  56.     // cout << dem;
  57.  
  58.     // ===== BFS tìm đường ngắn nhất + ăn nhiều điểm nhất đến các ô lon =====
  59.     vector<vector<ll>> dist(m + 1, vector<ll>(n + 1, 1e9));
  60.     vector<vector<ll>> score(m + 1, vector<ll>(n + 1, 0));
  61.     queue<ii> q;
  62.  
  63.     dist[x][y] = 0;
  64.     score[x][y] = mang[x][y];
  65.     q.push({x, y});
  66.  
  67.     while (!q.empty())
  68.     {
  69.         auto [u, v] = q.front();
  70.         q.pop();
  71.  
  72.         for (int dir = 0; dir < 4; dir++)
  73.         {
  74.             int nx = u + dx[dir];
  75.             int ny = v + dy[dir];
  76.             if (nx < 1 || ny < 1 || nx > m || ny > n)
  77.                 continue;
  78.  
  79.             ll newScore = score[u][v] + mang[nx][ny];
  80.  
  81.             if (dist[nx][ny] > dist[u][v] + 1)
  82.             {
  83.                 dist[nx][ny] = dist[u][v] + 1;
  84.                 score[nx][ny] = newScore;
  85.                 q.push({nx, ny});
  86.             }
  87.             else if (dist[nx][ny] == dist[u][v] + 1 && score[nx][ny] < newScore)
  88.             {
  89.                 score[nx][ny] = newScore;
  90.                 q.push({nx, ny});
  91.             }
  92.         }
  93.     }
  94.  
  95.     // ===== Tính ans lớn nhất trực tiếp tại đây =====
  96.     for (auto [i, j] : lon)
  97.     {
  98.         if (dist[i][j] <= t)
  99.         {
  100.             max_val = 0;
  101.             if (i > 1)
  102.                 max_val = max(max_val, mang[i - 1][j]);
  103.             if (j > 1)
  104.                 max_val = max(max_val, mang[i][j - 1]);
  105.             if (i < m)
  106.                 max_val = max(max_val, mang[i + 1][j]);
  107.             if (j < n)
  108.                 max_val = max(max_val, mang[i][j + 1]);
  109.  
  110.             if ((t - dist[i][j]) % 2 == 0)
  111.             {
  112.                 ans = max(ans, score[i][j] + ((t - dist[i][j]) / 2) * (max_val + mang[i][j]));
  113.             }
  114.             else
  115.             {
  116.                 ans = max(ans, score[i][j] + (((t - dist[i][j]) - 1) / 2) * (max_val + mang[i][j]) + max_val);
  117.             }
  118.         }
  119.     }
  120.  
  121.     // Nếu không đến được ô ma nào thì vẫn lấy đường đi tốt nhất trong t bước
  122.     ll fallback = 0;
  123.     for (ll i = 1; i <= m; i++)
  124.         for (ll j = 1; j <= n; j++)
  125.             if (dist[i][j] <= t)
  126.                 fallback = max(fallback, score[i][j]);
  127.  
  128.     cout << max(ans, fallback);
  129. }
  130.  
  131. int main()
  132. {
  133.     ios_base::sync_with_stdio(NULL);
  134.     cin.tie(0);
  135.     cout.tie(0);
  136.     solve();
  137. }
  138.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ET3naF
language:
C++ (gcc 8.3)
created:
10 days 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!