daily pastebin goal
69%
SHARE
TWEET

Untitled

a guest Nov 11th, 2015 167 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.         int n,m=0;
  10.        
  11.         cin >> n;
  12.         cin >> m;
  13.        
  14.         int**grid = new int*[n]();
  15.         for(int i =0;i<n;i++)
  16.         {
  17.                 grid[i] = new int[n]();
  18.                 for(int j =0;j<n;j++)
  19.                 {
  20.                         cin >> grid[i][j];
  21.                 }
  22.                
  23.         }
  24.        
  25.        
  26.        
  27. //      int** charms = new int*[m]();
  28.         int* safe = new int[n*n]();
  29.         for(int i =0;i<m;i++)
  30.         {
  31.                 int* charms = new int[3]();
  32.                 cin >> charms[0];
  33.                 cin >> charms[1];
  34.                 cin >> charms[2];
  35.                 for(int x = -charms[2]; x <= charms[2]; x++)
  36.                 {
  37.                         for(int y = charms[2] - abs(x); y >= -(charms[2] - abs(x)); y-- )
  38.                         {
  39.                                 int x1 = charms[0] + x;
  40.                                 int y1 = charms[1] + y;
  41.                                 if(x1 > 0 && y1 > 0 && x1 < n+1 && y1 < n+1)
  42.                                                 safe[(x1-1)*n + y1 - 1] = 1;
  43.                         }
  44.                 }
  45.         }
  46.        
  47.  
  48.        
  49.         int** dp = new int*[n*n];
  50.         int out = 0;
  51.         if(safe[0] == 1)
  52.         {
  53.        
  54.         for(int i =0;i<n;i++)
  55.         {
  56.                 for(int j =0;j<n;j++)
  57.                 {
  58.                         dp[i* (n) +j] = new int[2]();
  59.                         if(i==0 && j== 0 && safe[0] == 1)
  60.                                 {
  61.                                         dp[0,0] = grid[0,0];
  62.                                        
  63.                                         dp[0,1] = grid[0,0];
  64.                                 }
  65.                         if(safe[i *n +j] == 1)
  66.                         {
  67.                                 if(j>0 && safe[i *n +j-1] == 1)
  68.                                         dp[i*n + j][0] = max(dp[i*n + j-1][0], dp[i*n + j-1][1]) != 0 ? grid[i][j] + max(dp[i*n + j-1][0], dp[i*n + j-1][1]) : 0;
  69.                                
  70.                                 if(i>0 && safe[(i -1)*n +j] == 1)
  71.                                          dp[i*n + j][1] = max(dp[(i-1)*n + j][0], dp[(i-1)*n + j][1]) != 0 ? grid[i][j] + max(dp[(i-1)*n + j][0], dp[(i-1)*n + j][1]) : 0;
  72.                                
  73.                         //      cout << i<<","<<j<<":" << dp[i*n + j][0]<<":"<< dp[i*n + j][1]<<"\n";
  74.                         }
  75.                 }
  76.         }
  77.  
  78.         out = max(dp[n*n - 1][0], dp[n*n - 1][1]);
  79. }
  80.         if(out == 0)
  81.                 cout << "NO\n";
  82.         else{
  83.                 cout << "YES\n";
  84.                 cout << out;
  85.         }
  86. }
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