SHARE
TWEET

Untitled

a guest Aug 19th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <vector>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int price[42];
  10. int cnt[42];
  11. int mat[20][20];
  12.  
  13. int dx[4] = { 1, -1, 0, 0 };
  14. int dy[4] = { 0, 0, 1, -1 };
  15.  
  16. int main(void) {
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.  
  20.     for (int i = 1; i <= 41; i++) {
  21.         price[i] = i*i + (i - 1)*(i - 1);
  22.     }
  23.     int tc;
  24.     cin >> tc;
  25.     for (int test_case = 1; test_case <= tc; test_case++) {
  26.         int n, m;
  27.         cin >> n >> m;
  28.         vector<pair<int, int>> homelist;
  29.         for (int i = 0; i < n; i++) {
  30.             for (int j = 0; j < n; j++) {
  31.                 cin >> mat[i][j];
  32.                 if (mat[i][j] == 1) {
  33.                     homelist.push_back(make_pair(i, j));
  34.                 }
  35.             }
  36.         }
  37.  
  38.         int ans = 0;
  39.         for (int i = 0; i < n; i++) {
  40.             for (int j = 0; j < n; j++) {
  41.                 memset(cnt, 0, sizeof(cnt));
  42.                 int maxdist = -1;
  43.                 for (int k = 0; k < homelist.size(); k++) {
  44.                     int x = homelist[k].first;
  45.                     int y = homelist[k].second;
  46.                    
  47.                         // ์ž๊ธฐ ์ž์‹ ๋ถ€ํ„ฐ 1์ด๊ธฐ ๋•Œ๋ฌธ์— 1์„ ๋”ํ•ด์•ผ
  48.                     int distance = abs(i - x) + abs(j - y) + 1;
  49.                     cnt[distance] += 1;
  50.                     maxdist = max(maxdist, distance);
  51.                 }
  52.  
  53.                 for (int k = 1; k <= maxdist; k++) {
  54.                     cnt[k] += cnt[k - 1];
  55.                 }
  56.  
  57.                 int tmpmax = -1;
  58.                 for (int k = 1; k <= maxdist; k++) {
  59.                     int tmpprice = m * cnt[k] - price[k];
  60.                     if (tmpprice >= 0) {
  61.                         tmpmax = max(tmpmax, cnt[k]);
  62.                     }
  63.                 }
  64.  
  65.                 ans = max(ans, tmpmax);
  66.             }
  67.         }
  68.  
  69.         cout << "#" << test_case << " " << ans << '\n';
  70.     }
  71.    
  72.     return 0;
  73. }
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