fork download
copy 
  1.  
  2. #include <cassert>
  3. #include <cctype>
  4. #include <cerrno>
  5. #include <cfloat>
  6. #include <ciso646>
  7. #include <climits>
  8. #include <clocale>
  9. #include <cmath>
  10. #include <csetjmp>
  11. #include <csignal>
  12. #include <cstdarg>
  13. #include <cstddef>
  14. #include <cstdio>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <ctime>
  18. #include <ccomplex>
  19. #include <cfenv>
  20. #include <cinttypes>
  21. #include <cstdbool>
  22. #include <cstdint>
  23. #include <ctgmath>
  24. #include <cwchar>
  25. #include <cwctype>
  26. #include <algorithm>
  27. #include <bitset>
  28. #include <complex>
  29. #include <deque>
  30. #include <exception>
  31. #include <fstream>
  32. #include <functional>
  33. #include <iomanip>
  34. #include <ios>
  35. #include <iosfwd>
  36. #include <iostream>
  37. #include <istream>
  38. #include <iterator>
  39. #include <limits>
  40. #include <list>
  41. #include <locale>
  42. #include <map>
  43. #include <memory>
  44. #include <new>
  45. #include <numeric>
  46. #include <ostream>
  47. #include <queue>
  48. #include <set>
  49. #include <sstream>
  50. #include <stack>
  51. #include <stdexcept>
  52. #include <streambuf>
  53. #include <string>
  54. #include <typeinfo>
  55. #include <utility>
  56. #include <valarray>
  57. #include <vector>
  58. #include <array>
  59. #include <atomic>
  60. #include <chrono>
  61. #include <condition_variable>
  62. #include <forward_list>
  63. #include <future>
  64. #include <initializer_list>
  65. #include <mutex>
  66. #include <random>
  67. #include <ratio>
  68. #include <regex>
  69. #include <scoped_allocator>
  70. #include <system_error>
  71. #include <thread>
  72. #include <tuple>
  73. #include <typeindex>
  74. #include <type_traits>
  75. #include <unordered_map>
  76. #include <unordered_set>
  77.  
  78. using namespace std;
  79. #define pb push_back
  80. #define eb emplace_back
  81. #define mp make_pair
  82. #define pii pair<int,int>
  83. #define pll pair<long long , long long>
  84. #define vi vector<int>
  85. #define vpii vector<pii>
  86. #define SZ(x) ((int)(x.size()))
  87. #define fi first
  88. #define se second
  89. #define IN(x,y) ((y).find((x))!=(y).end())
  90. #define ALL(t) t.begin(),t.end()
  91. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  92. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  93. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  94. #define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
  95. #define dem(x) __builtin_popcount(x)
  96. #define Mask(x) (1LL << (x))
  97. #define BIT(x, i) ((x) >> (i) & 1)
  98. #define ln '\n'
  99. #define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  100. ///mt19937 rnd(time(0));
  101.  
  102. const int INF = 1e9 , mod = 1e9 + 7;
  103.  
  104. template <class T1, class T2>
  105. inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }
  106.  
  107. template <class T1 , class T2>
  108. inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}
  109.  
  110. template <class T>
  111. inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }
  112.  
  113. template <class T>
  114. inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }
  115.  
  116. template <class T>
  117. inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }
  118.  
  119. template <class T>
  120. inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }
  121.  
  122. #define PROB "formation"
  123. void file(){
  124.     if(fopen(PROB".inp", "r")){
  125.         freopen(PROB".inp","r",stdin);
  126.         freopen(PROB".out","w",stdout);
  127.     }
  128. }
  129. void sinh_(){
  130. //    srand(time(0));
  131. //    freopen(PROB".inp" , "w" , stdout);
  132. //    int n;
  133. }
  134.  
  135. typedef long long ll;
  136. typedef double db;
  137. const int N = 2e3 + 5;
  138. const int dx[] = {-1, 1, 0, 0};
  139. const int dy[] = {0, 0, -1, +1};
  140. const int maxn = 2e3;
  141.  
  142. int n, m, k;
  143. bool a[N][N], b[N][N];
  144. int dist[N][N] = {}, d[N][N];
  145. ll ans[N][N] = {}, Ans[N][N];
  146. ll res = 0;
  147. int pre_cnt[N*2][N*2] = {};
  148. pair<ll, int> t[N][N] = {}, r[N][N] = {}, diagon[N * 2];
  149.  
  150. void readip(){
  151.     cin >> n >> m >> k;
  152.     REP(i, 1, n) REP(j, 1, m) cin >> a[i][j];
  153. }
  154.  
  155. int cal(int x, int y, int xx, int yy) {
  156.     maximize(x, 1 - m);
  157.     minimize(xx, n - 1);
  158.     maximize(y, 2);
  159.     minimize(yy, n + m);
  160.     return pre_cnt[xx + maxn][yy] 
  161.  
  162.         + pre_cnt[x - 1 + maxn][y - 1] 
  163.         - pre_cnt[x - 1 + maxn][yy] 
  164.         - pre_cnt[xx + maxn][y - 1];
  165. }
  166.  
  167. void sub5() {
  168.     vector<vi> dist(n + 2, vi(m + 2, -1));
  169.     queue<pii> q;
  170.     REP(i, 1, n) REP(j, 1, m) if (a[i][j]) {
  171.         dist[i][j] = 0;
  172.         q.push(mp(i, j));
  173.     }
  174.     while(!q.empty()) {
  175.         int x = q.front().fi;
  176.         int y = q.front().se;
  177.         q.pop();
  178.         FOR(i, 4) {
  179.             int nx = x + dx[i], ny = y + dy[i];
  180.             if (nx < 0 || nx > n || ny < 0 || ny > m || dist[nx][ny] != -1) continue;
  181.             dist[nx][ny] = dist[x][y] + 1;
  182.             q.push(mp(nx, ny));
  183.         }
  184.     }
  185.     ll res = 0;
  186.     REP(i, 1, n) REP(j, 1, m) res += dist[i][j];
  187.     cout << res << ln;
  188. }
  189.  
  190.  
  191. void prepare() {
  192.     REP(i, 1, n) REP(j, 1, m) if (a[i][j]) 
  193.         pre_cnt[i - j + maxn][i + j] += 1;
  194.  
  195.     REP(i, 1 - m + maxn, n - 1 + maxn)  REP(j, 2, n + m) 
  196.         pre_cnt[i][j] += pre_cnt[i - 1][j] + pre_cnt[i][j - 1] - pre_cnt[i - 1][j - 1];
  197.  
  198.     memset(dist, -1, sizeof dist);
  199.     REP(d, 0, n + m) {
  200.         int tmp = cal(1 - 1 - d , 1 + 1 - d, 1 - 1 + d, 1 + 1 + d);
  201.         if (tmp >= k) {
  202.             dist[1][1] = d;
  203.             res -= 1LL * (tmp - k) * d;
  204.             break;
  205.         }
  206.     }
  207.  
  208.     assert(dist[1][1] != -1);
  209.  
  210.     REP(i, 1, n) REP(j, 1, m) {
  211.         if (i == 1 && j == 1) continue;
  212.         int D = (j == 1) ? dist[i - 1][j] : dist[i][j - 1];
  213.         REP(d, D - 1, D + 1) {
  214.             int tmp = cal(i - j - d, i + j - d, i - j + d, i + j + d);
  215.             if (tmp >= k) {
  216.                 dist[i][j] = d;
  217.                 res -= 1LL * (tmp - k) * d;
  218.                 break;
  219.             }
  220.         }
  221.         assert(dist[i][j] != -1);
  222.     }
  223. }
  224.  
  225. void xoay() { // i j -> j, n - i + 1
  226.     REP(i, 1, n) REP(j, 1, m) {
  227.         b[j][n - i + 1] = a[i][j];
  228.         d[j][n - i + 1] = dist[i][j];
  229.         Ans[j][n - i + 1] = ans[i][j];
  230.     }
  231.  
  232.     swap(n, m);
  233.  
  234.     REP(i, 1, n) REP(j, 1, m) {
  235.         a[i][j] = b[i][j];
  236.         dist[i][j] = d[i][j];
  237.         ans[i][j] = Ans[i][j];
  238.     }
  239. }
  240.  
  241. void solve(){  
  242.     if (k == 1) {
  243.         sub5();
  244.         return;
  245.     }
  246.  
  247.     prepare();  
  248.     FOR(dir, 4) {
  249.         REP(i, 0, n + m) diagon[i] = mp(0LL, 0);
  250.         REP(i, 0, n + 1) REP(j, 0, m + 1) t[i][j] = mp(0, 0), r[i][j] = mp(0, 0);
  251.  
  252.         REP(i, 1, n) REPD(j, m, 1) {
  253.             t[i][j].fi = (a[i][j] ? i + j : 0) + t[i - 1][j].fi + t[i - 1][j + 1].fi - (i <= 2 ? 0 : t[i - 2][j + 1].fi);
  254.             t[i][j].se = (a[i][j] ? 1 : 0)     + t[i - 1][j].se + t[i - 1][j + 1].se - (i <= 2 ? 0 : t[i - 2][j + 1].se);   
  255.  
  256.             r[i][j].fi = (a[i][j] ? i + j : 0) + r[i - 1][j].fi + r[i][j + 1].fi - r[i - 1][j + 1].fi;
  257.             r[i][j].se = (a[i][j] ? 1 : 0)     + r[i - 1][j].se + r[i][j + 1].se - r[i - 1][j + 1].se;
  258.  
  259.             diagon[i + j].fi += (a[i][j] ? i + j : 0);
  260.             diagon[i + j].se += (a[i][j] ? 1 : 0);
  261.         }
  262.  
  263.  
  264.  
  265.         REP(i, 2, n + m) {
  266.             diagon[i].fi += diagon[i - 1].fi;
  267.             diagon[i].se += diagon[i - 1].se;
  268.         }
  269.  
  270.         REP(i, 1, n) REP(j, 1, m) {
  271.             ll sum = t[min(n, i + dist[i][j])][j].fi - r[i - 1][j].fi;
  272.             int cnt = t[min(n, i + dist[i][j])][j].se - r[i - 1][j].se;
  273.  
  274.             if (j + dist[i][j] + 1 <= m)  {
  275.                 sum -= t[i - 1][j + dist[i][j] + 1].fi;
  276.                 sum += r[i - 1][j + dist[i][j] + 1].fi;
  277.  
  278.                 cnt -= t[i - 1][j + dist[i][j] + 1].se;
  279.                 cnt += r[i - 1][j + dist[i][j] + 1].se;
  280.             }
  281.  
  282.  
  283.             if (i + dist[i][j] > n) {
  284.                 int l = n + j + 1, r = min(n + m, i + j + dist[i][j]);
  285.                 if (l <= r) {
  286.                     sum += diagon[r].fi - diagon[l - 1].fi;
  287.                     cnt += diagon[r].se - diagon[l - 1].se;
  288.                 }
  289.             }
  290.  
  291.             ans[i][j] += sum - 1LL * (i + j) * cnt;
  292.         }
  293.         xoay();
  294.     }
  295.  
  296.  
  297.     REP(i, 1, m) r[0][i] = mp(0, 0);
  298.     REP(i, 1, n) REP(j, 1, m) {
  299.         r[i][j].fi = r[i - 1][j].fi + (a[i][j] ? i : 0);
  300.         r[i][j].se = r[i - 1][j].se + (a[i][j] ? 1 : 0);
  301.     }
  302.  
  303.     REP(i, 1, n) REP(j, 1, m) {
  304.         int L = max(1, i - dist[i][j]), R = i - 1;
  305.         if (L <= R) {
  306.             ll sum = r[R][j].fi - r[L - 1][j].fi;
  307.             int cnt = r[R][j].se - r[L - 1][j].se;
  308.             ans[i][j] -= 1LL * i * cnt - sum;
  309.         }
  310.         L = i + 1, R = min(n, i + dist[i][j]);
  311.         if (L <= R) {
  312.             ll sum = r[R][j].fi - r[L - 1][j].fi;
  313.             int cnt = r[R][j].se - r[L - 1][j].se;
  314.             ans[i][j] -= sum - 1LL * i * cnt;
  315.         }
  316.     }
  317.     REP(i, 1, n) r[i][0] = mp(0, 0);
  318.     REP(i, 1, n) REP(j, 1, m) {
  319.         r[i][j].fi = r[i][j - 1].fi + (a[i][j] ? j : 0);
  320.         r[i][j].se = r[i][j - 1].se + (a[i][j] ? 1 : 0);
  321.     }
  322.     REP(i, 1, n) REP(j, 1, m) {
  323.         int L = max(1, j - dist[i][j]), R = j - 1;
  324.         if (L <= R) {
  325.             ll sum = r[i][R].fi - r[i][L - 1].fi;
  326.             int cnt = r[i][R].se - r[i][L - 1].se;
  327.             ans[i][j] -= 1LL * j * cnt - sum;
  328.         }
  329.         L = j + 1, R = min(m, j + dist[i][j]);
  330.         if (L <= R) {
  331.             ll sum = r[i][R].fi - r[i][L - 1].fi;
  332.             int cnt = r[i][R].se - r[i][L - 1].se;
  333.             ans[i][j] -= sum - 1LL * j * cnt;
  334.         }
  335.     }
  336.  
  337.     REP(i, 1, n)  REP(j, 1, m) res += ans[i][j];
  338.     cout << res << ln;
  339. }
  340.  
  341. int main(){
  342.     sinh_();
  343.     io_faster
  344.     file();
  345.     int t = 1;
  346. //    cin >> t;
  347.     while (t--){
  348.         readip();
  349.         solve();
  350.     }
  351. }
  352.  
Success #stdin #stdout 0.01s 26164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/GoB3Ia
language:
C++14 (gcc 8.3)
created:
1 day 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!