cpp.cpp

#pragma GCC optimize "-O3"

#include <bits/stdc++.h>

using namespace std;

const int N = 3030;
const int M = 100100;

inline int read() {
    int ans = 0; char ch;
    for (ch = getchar(); ch < 48 || ch > 57; ch = getchar());
    for (; ch >=  48 && ch <= 57; ch = getchar())
        ans = (ans << 3) + (ans << 1) + (ch - 48);
    return ans;
}

struct info {
  int l, r, x, y;
  info(int l = 0,int r = 0,int x = 0,int y = 0) : l(l), r(r), x(x), y(y) {}
  bool operator < (const info &b) const {
    return make_pair(l, r) < make_pair(b.l, b.r);
  }
};

int n, m, k;
int a[N][N];
info val[N][N];
set<info> s[M];
int ad[N << 2], mx[N << 2];
int64_t sm[N << 2];

void push(int v,int l,int r) {
  if (ad[v]) {
    mx[v] += ad[v];
    sm[v] += (int64_t) ad[v] * (r - l + 1);
    if (l < r) {
      ad[v << 1] += ad[v];
      ad[v << 1 | 1] += ad[v];
    }
    ad[v] = 0;
  }
}

void pull(int v) {
  mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
  sm[v] = sm[v << 1] + sm[v << 1 | 1];
}

void upd(int v,int l,int r,int L,int R,int x) {
  push(v, l, r);
  if (L > r || R < l) return;
  if (L <= l && r <= R) {
    ad[v] = x;
    push(v, l, r);
    return;
  }
  int md = (l + r) >> 1;
  upd(v << 1, l, md, L, R, x);
  upd(v << 1 | 1, md + 1, r, L, R, x);
  pull(v);
}

void debug(int v,int l,int r) {
  push(v, l, r);
  if (v == 1) cout << '\n';
  if (l == r) {
    cout << mx[v] << ' ';
  } else {
    int md = (l + r) >> 1;
    debug(v << 1, l, md);
    debug(v << 1 | 1, md + 1, r);
  }
  if (v == 1) { cout << '\n';
  }
}

void add(int x,int y,int l,int r) {
  int v = a[x][y];

  auto &s = ::s[v];
  auto it = s.lower_bound(info(l, l, 0, 0));
  if (it != s.begin()) {
    --it;
    if (it->r < l) it++;
  }
  vector<info> toadd;
  vector<info> todel;
  while (it != s.end()) {
    int xx = it->x, yy = it->y, ll = it->l, rr = it->r;
    int tl = max(l, ll), tr = min(r, rr);
    if (tl > tr) break;
    upd(1, 1, m - k + 1, tl, tr, -1);
    if (tl == ll && tr == rr) {
      todel.push_back(*it);
      val[xx][yy] = {0, 0, xx, yy};
    } else if (ll < l) {
      todel.push_back(*it);
      val[xx][yy] = {ll, l - 1, xx, yy};
      toadd.push_back(val[xx][yy]);
    } else {
      todel.push_back(*it);
      val[xx][yy] = {r + 1, rr, xx, yy};
      toadd.push_back(val[xx][yy]);
    }
    it++;
  }
  for (auto u : toadd) s.insert(u);
  for (auto u : todel) s.erase(u);
  val[x][y] = {l, r, x, y};
  s.insert(val[x][y]);
  upd(1, 1, m - k + 1, l, r, 1);
}

void del(int x,int y) {
  int v = a[x][y];
  auto &s = ::s[v];
  int l = val[x][y].l, r = val[x][y].r;
  if (l && r) {
    s.erase(info(l, r, x, y));
    upd(1, 1, m - k + 1, l, r, -1);
  }
}

int main() {
  n = read(), m = read(), k = read();
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      a[i][j] = read();
    }
  }

  int mx = 0;
  int64_t sm = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int l = max(1, j - k + 1);
      int r = min(j, m - k + 1);
      add(i, j, l, r);
    }
    if (i > k) {
      for (int j = 1; j <= m; ++j) {
        del(i - k, j);
      }
    }
    if (i >= k) {
      mx = max(mx, ::mx[1]);
      sm += ::sm[1];
    }
  }
  printf("%d %lld\n", mx, sm);
}