daily pastebin goal
62%
SHARE
TWEET

Untitled

a guest Dec 5th, 2014 269 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n, m, k;
  6. bool safe[505][505] = { };
  7. int best[505][505], val[505][505];
  8.  
  9. int main()
  10. {
  11.         ios::sync_with_stdio(false);
  12.  
  13.         cin >> n >> m;
  14.  
  15.         for(int i = 1; i <= n; i++)
  16.         {
  17.                 for(int j = 1; j <= n; j++)
  18.                 {
  19.                         cin >> val[i][j];
  20.                         best[i][j] = -2000000000;
  21.                 }
  22.         }
  23.  
  24.         for(int i = 0; i < m; i++)
  25.         {
  26.                 int r, c, k;
  27.                 cin >> r >> c >> k;
  28.                 for(int p = r - k; p < r; p++)
  29.                 {
  30.                         if(p < 1) continue;
  31.                         for(int q = c - (p - (r - k)); q <= c + (p - (r - k)); q++)
  32.                         {
  33.                                 if(q < 1) continue;
  34.                                 if(q > n) break;
  35.                                 safe[p][q] = true;
  36.                         }
  37.                 }
  38.                 for(int q = c - k; q <= c + k; q++)
  39.                 {
  40.                         safe[r][q] = true;
  41.                 }
  42.                 for(int p = r + 1; p <= r + k; p++)
  43.                 {
  44.                         if(p > n) break;
  45.                         for(int q = c - k + (p - r); q <= c + k - (p - r); q++)
  46.                         {
  47.                                 if(q < 1) continue;
  48.                                 if(q > n) break;
  49.                                 safe[p][q] = true;
  50.                         }
  51.                 }
  52.         }
  53.  
  54.         best[1][1] = val[1][1];
  55.         for(int i = 1; i <= n; i++)
  56.         {
  57.                 for(int j = 1; j <= n; j++)
  58.                 {
  59.                         if(!safe[i][j] || best[i][j] == -2000000000) continue;
  60.                         best[i + 1][j] = max(best[i + 1][j], best[i][j] + val[i + 1][j]);
  61.                         best[i][j + 1] = max(best[i][j + 1], best[i][j] + val[i][j + 1]);
  62.                 }
  63.         }
  64.  
  65.         if(best[n][n] == -2000000000) cout << "NO";
  66.         else cout << "YES\n" << best[n][n];
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top