daily pastebin goal
65%
SHARE
TWEET

Untitled

a guest Jan 9th, 2015 192 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int dp[1002][1002];
  5. int a[1001][1001];
  6.  
  7. int main()
  8. {
  9.     cin.tie(0);
  10.     ios::sync_with_stdio(false);
  11.     int n,m;
  12.     cin >> n >> m;
  13.     for(int i = 0;i < n;i++)
  14.         for(int j = 0;j < m;j++)
  15.             cin >> a[i][j];
  16.     int c;
  17.     cin >> c;
  18.     dp[1][1] = a[0][0];
  19.     for(int i = 0;i <= n;i++) dp[i][0] = 0;
  20.     for(int j = 0;j <= m;j++) dp[0][j] = 0;
  21.     for(int i = 2;i <= n;i++) dp[i][1] = a[i-1][0] + dp[i-1][1];
  22.     for(int i = 2;i <= m;i++) dp[1][i] = a[0][i-1] + dp[1][i-1];
  23.     for(int i = 2;i <= n;i++)
  24.         for(int j = 2;j <= m;j++)
  25.             dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1];
  26.  
  27.     //***DEBUG***
  28.  
  29.     /*cout << endl;
  30.     for(int i = 0;i < n+1;i++)
  31.     {
  32.         for(int j = 0;j < m+1;j++)
  33.             cout << dp[i][j] << " ";
  34.         cout << endl;
  35.     }
  36.     cout << endl;*/
  37.  
  38.     for(int ctr = 0;ctr < c;ctr++)
  39.     {
  40.         int x1,y1,x2,y2;
  41.         cin >> x1 >> y1 >> x2 >> y2;
  42.         cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << '\n';
  43.     }
  44.     return 0;
  45. }
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