Post 38

Veröffentlicht am

好几天由于各种事情结果没写blog

把最近做的题写写题解

[NOI2015]程序自动分析

题目描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入输出格式

输入格式：

从文件prog.in中读入数据。

输入文件的第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若�e=0，则该约束条件为xi≠xj；

输出格式：

输出到文件 prog.out 中。

输出文件包括t行。

输出文件的第 k行输出一个字符串“ YES” 或者“ NO”（不包含引号，字母全部大写），“ YES” 表示输入中的第k个问题判定为可以被满足，“ NO” 表示不可被满足。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
6
7
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出样例#1：

复制

1
2
NO
YES

输入样例#2：

复制

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出样例#2：

复制

1
2
YES
NO

说明

【样例解释1】

在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1=x2,x1=x2。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：x1=x2,x2=x3,x3=x1。只需赋值使得x1=x1=x1，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：x1=x2,x2=x3,x3=x4,x4≠x1。由前三个约束条件可以推出x1=x2=x3=x4，然而最后一个约束条件却要求x1≠x4，因此不可被满足。

【数据范围]

img

【时限2s，内存512M】

题解

一道十分sb的并查集，结果由于我坐着硬刚掉进思维陷阱结果这道多日来做的最简单的题我却看了题解。。

这道题一开始想用扩展域，后来想了一想发现不等关系没有传递性。

然后就魔改扩展域并查集不过还是失败了。

我当时为什么没想到既然这样不等关系就是相对独立的，因此没有必要管它呢？（其实确实需要一点灵感才能想到）

我们只需要把相等的合并了，然后看看不等的两个变量属不属于一个集合就行了。。

这道题就怕想不到不等关系

Code：

1
2


[1007]Scarlet的字符串不可能这么可爱

题目描述

Scarlet妄图构造字符集为kk，长度为LL的字符串，满足没有任何一个长度超过11的回文连续子串。

看起来这样的字符串太多了，Scarlet随手加了个限制：她指定了字符串的第ss位为ww。

这下Scarlet不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对pp取模后的结果。

输入输出格式

输入格式：

第一行三个整数k,Lk,L和pp，分别表示构造的字符串的的字符集、长度和模数。

第二行两个整数s,ws,w，描述Scarlet给的限制。

注意：s=0s=0表示该数据点中Scarlet十分良心地没有添加限制

输出格式：

一行一个整数，表示答案对pp的取模后的结果。

输入输出样例

输入样例#1：

1
2
3 3 233
1 1

输出样例#1：

1
2

说明

字符集：一个字符串中不同字符的数量。例如，字符集是3的话，你可以认为字符串仅由“A”、“B”、“C”三个字母组成。

样例解释：第一个字符固定A，那么符合要求的字符串是ABC,ACB。而AAB字符串包括AA这个回文子串，ACA本身就是回文串，一次类推。

对于$100\%$的数据$1\leq k,L\leq 10^{18},0\leq s\leq L,1\leq w\leq k,1\leq p\leq 10^9$

题解

这道题首先要想到位置不同方案数是相同的。

如果指定字符呢？其实也没有什么大不了的，在前面我们可以发现每一个字符会对后两位进行限制，那么这个指定的字符只是会对前后两位有限制。

通过计算会发现就是没有限制的情况 除$k$即可，

我记得当时比赛我并没有想出来这一点，思维能力=-INF

后面的就好推了。

我们发现递推的时候对于第$k$位（$k >= 3$），只需要和前一位与前两位不同即可，因为我们每一位始终保证没有回文串，意味着和$k-3$位相同，$k-2$与$k-1$会阻隔他们形成回文串。

会这个简单的性质你就可以80分啦。

结合上面，我们就可以通过这道题。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define LL long long 
LL ans , mod , k , n;

inline LL pow(LL n , LL k)
{
	LL ans = 1 , base = n % mod;
	for( ; k ; k >>= 1 , base = base * base % mod)
		if(k & 1)
			ans = ans * base % mod;
	return ans;
}
LL s;
inline LL solve()
{
	k %= mod;
	if(s > 0){
		if(n == 1) return 1;
		if(n == 2) return (k-1) % mod;
		return (k-1) % mod * pow(k-2,n-2) % mod;
	}
	else {
		if(n == 1) return k % mod;
		if(n == 2) return k % mod * (k-1) % mod;
		return k % mod * (k-1) % mod * pow(k-2,n-2) % mod;
	}
}


int main()
{
	 LL t;
	scanf("%lld%lld%lld",&k,&n,&mod);
	scanf("%lld%lld",&s,&t);
	printf("%lld\n",solve());
}

玉蟾宫

题目背景

有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

题目描述

这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。

现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。

但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。

输入输出格式

输入格式：

第一行两个整数N,M，表示矩形土地有N行M列。

接下来N行，每行M个用空格隔开的字符’F’或’R’，描述了矩形土地。

输出格式：

输出一个整数，表示你能得到多少银子，即(3*最大’F’矩形土地面积)的值。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 6 
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

输出样例#1：

1
45

说明

$1<=N,M<=1000$

题解

终于认真学习了悬线法。。。（还有另一种求极大有效子矩形的算法）

这破玩意边界真多啊。。联赛不会考这么板子的题的，mhr如是毒奶道。

其实我们只是尽量有效的枚举极大子矩形就可以。

对于每个点，它向上最大没有障碍点的距离称为悬线，然后预处理出左右能使悬线有效的长度。

可以画图证明其正确性。

注意边界以及左右是两开的，所以左右多扩展一位表示直到左右边界都没有障碍。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1005
int h[maxn][maxn] , l[maxn][maxn] , r[maxn][maxn] , n , m;
bool vld[maxn][maxn];
char ch;

int main()
{
//	freopen("data.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
		{
			std::cin>>ch;
			if(ch == 'R') vld[i][j] = true;
		}
	for(int i = 1 ; i <= m ; ++i)
		l[0][i] = 0 , r[0][i] = m + 1;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			if(!vld[i][j]) h[i][j] = h[i-1][j] + 1;
			else h[i][j] = 0;
		}
		for(int j = 1 , t = 0 ; j <= m ; ++j)
		{
			if(!vld[i][j]) l[i][j] = std::max(l[i-1][j] , t);
			else t = j ;
		}
		for(int j = m , t = m + 1; j >= 1 ; --j)
		{
			if(!vld[i][j]) r[i][j] = std::min(r[i-1][j] , t);
			else t = j , r[i][j] = m + 1;
		}
	}
//	for(int i = 1 ; i <= n ; ++i)
//		for(int j = 1 ; j <= m ; ++j)
//			printf("%d %d %d %d %d\n",i,j,h[i][j],l[i][j],r[i][j]);
	int ans = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			ans = std::max(ans , (r[i][j] - l[i][j] - 1) * h[i][j]);
	printf("%d",ans * 3);
}

[USACO15JAN]电影移动Moovie Mooving

题目描述

Bessie is out at the movies. Being mischievous as always, she has decided to hide from Farmer John for L (1 <= L <= 100,000,000) minutes, during which time she wants to watch movies continuously. She has N (1 <= N <= 20) movies to choose from, each of which has a certain duration and a set of showtimes during the day. Bessie may enter and exit a movie at any time during one if its showtimes, but she does not want to ever visit the same movie twice, and she cannot switch to another showtime of the same movie that overlaps the current showtime.

Help Bessie by determining if it is possible for her to achieve her goal of watching movies continuously from time 0 through time L. If it is, determine the minimum number of movies she needs to see to achieve this goal (Bessie gets confused with plot lines if she watches too many movies).

奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。

贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

请帮贝西计算她能够做到从0到L分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。

输入输出格式

输入格式：

INPUT: (file movie.in)

The first line of input contains N and L.

The next N lines each describe a movie. They begin with its integer duration, D (1 <= D <= L) and the number of showtimes, C (1 <= C <= 1000). The remaining C integers on the same line are each in the range 0..L, and give the starting time of one of the showings of the movie. Showtimes are distinct, in the range 0..L, and given in increasing order.

输出格式：

UTPUT: (file movie.out)

A single integer indicating the minimum number of movies that Bessie

needs to see to achieve her goal. If this is impossible output -1

instead.

输入输出样例

输入样例#1：

1
2
3
4
5
4 100 
50 3 15 30 55 
40 2 0 65 
30 2 20 90 
20 1 0

输出样例#1：

1
3

说明

SOLUTION NOTES:

Bessie should attend the first showing of the fourth movie from time 0

to time 20. Then she watches the first showing of the first movie

from time 20 to time 65. Finally she watches the last showing of the

second movie from time 65 to time 100.

题解

一道还行的状态压缩dp

我一开始写了个爆搜得了个位数。。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 22
std::vector<int> v[maxn];
int n , c , l[maxn] , len , ans;
bool vis[maxn];

void dfs(int cur , int ct , int dep)
{
    if(dep > (int)n*1.5) return;
    if(cur >= len) {
        ans = std::min(ans , ct);
        return ;
    }

    for(int i = 1 ; i <= n ; ++i)
    {
        if(vis[i]) continue;
        if(v[i][0] > cur) break;
        vis[i] = true; // choose it
        for(int j = 0 ; j < (int)v[i].size() ; ++j)
        {
            if(v[i][j] > cur || v[i][j] + v[i].back() < cur) continue;
            dfs(v[i][j] + v[i].back() , ct + 1 , dep + 1);
        }
        vis[i] = false; // not choose or choose later
        dfs(cur , ct , dep + 1);
    }
}
        
bool operator < (const std::vector<int>& x , const std::vector<int>& y){
    return x[0] < y[0];
}	
int main()
{
    scanf("%d%d",&n,&len);
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%d%d",&l[i],&c);
        int x;
        for(int j = 1 ; j <= c ; ++j)
            scanf("%d",&x) , v[i].push_back(x);
    }
    for(int i = 1 ; i <= n ; ++i)
        v[i].push_back(l[i]);
    std::sort(v+1,v+n+1);
    ans = 0x7ffffff;
    dfs(0,0,0);
    if(ans > 20) ans = -1;
    printf("%d\n",ans);
}

然后想状态压缩dp做法，突然我眉头一皱，目光停在一句看上去很平常的话上：
贝西可以在一部电影播放过程中的任何时间进入或退出放映厅

那不就是对于任意一个已经观看的电影状态，都是越大越好吗？？

反正可以中途进入，那大了在进入和比较小进入最后的结束时间是一样的。

这个小贪心没什么问题。

她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅

直接算结束时间更新即可。

然后我们对于当前的状态和枚举的下一个准备看的电影，只需要在电影的开始时间里找当前状态值的前驱，然后算出看完的时间更新当前状态并上这个电影的状态就行。

然后注意判断-1.

然后就随便过了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define maxn 22
std::vector<int> v[maxn];
int n , c , l[maxn] , len , ans , f[1<<maxn];
bool vis[maxn];

inline int bit(int x){
	int ans = 0;
	for( ; x ; x -= x & -x)
		++ans;
	return ans;
}

inline int find(int k , int val)
{
	std::vector<int>& now = v[k];
	int cl = 0 , cr = now.size() - 1 , ans = -0x7ffffff;
	while(cl <= cr)
	{
		int mid = cl + cr >> 1;
		if(now[mid] <= val) ans = now[mid] , cl = mid + 1;
		else cr = mid - 1;
	}
	return ans + l[k];
}

void write(int x)
{
	std::stack<int> k;
	for( ; x ; x >>= 1)
		k.push(x&1);
	for( ; k.size() ; k.pop())
		putchar(k.top()+48);
	putchar(32);
}

int main()
{
	scanf("%d%d",&n,&len);
	for(int i = 1; i <= n ; ++i)
	{
		scanf("%d%d",&l[i],&c);
		for(int j = 1 , x; j <= c ; ++j)
			scanf("%d",&x) , v[i].push_back(x);
	}
	std::memset(f,-0x7f,sizeof(f));
	f[0] = 0;
	int S = 1 << n;
	for(int i = 0 ; i < S ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
		{
			if(i & (1 << j - 1)) continue;
			f[i | (1 << j - 1)] = std::max(f[i | (1 << j - 1)] , find(j , f[i]));
		}
	}
//	for(int i = 1 ; i < S ; ++i)
//		write(i) , printf("%d\n",f[i]);
	int ans = 0x7fffff;
	for(int i = 1 ; i < S ; ++i)
		if(f[i] >= len)
			ans = std::min(ans , bit(i));
	if(ans > n) ans = -1;
	printf("%d",ans);
}

[HAOI2007]理想的正方形

题目描述

有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入输出格式

输入格式：

第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：

仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

输出样例#1：

1
1

说明

$2<=a,b<=1000,n<=a,n<=b,n<=100$

题解

定长区间+最大最小值的合并性质让我们可以用单调队列来处理这道题。

首先我们思考一下边长为$n$的正方形的最大值是什么（形而上）：

是$n$个上下连续的长度为$n$的小长方形的最大值的最大值。

那我们先用单调队列求出所有长度为$n$的小长方形的最大值，然后再单调队列竖着求所有$n$个连续小长方形构成的边长为$n$的正方形的最大值就可以了。

手写Deque优化常数。

时间复杂度$\Theta(ab)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 1005
int a , b , n , p[maxn][maxn] , f[maxn][maxn] , g[maxn][maxn] , xmx[maxn][maxn] , xmn[maxn][maxn];

struct Deque
{
    int l , r , q[maxn];
    Deque(){
        l = 1 , r = 0;
    //	std::memset(q,0,sizeof(q));
    }
    inline void clear(){
        l = 1 , r = 0;
    //	std::memset(q,0,sizeof(q));
    }
    inline void push(int x){
        q[++r] = x;
    }
    inline int size(){
        return r-l+1;
    }
    inline int front(){
        return q[l];
    }
    inline int back(){
        return q[r];
    }
    inline void pop_back(){
        q[r--] = 0;
    }
    inline void pop_front(){
        q[l++] = 0;
    }
}q;

inline void solve()
{
    for(int i = 1 ; i <= a ; ++i)
    {
        q.clear();
        int* now = p[i];
        for(int j = 1 ; j <= b ; ++j)
        {
            while(q.size() && now[j] > now[q.back()]) q.pop_back();
            while(q.size() && j - q.front() + 1 > n) q.pop_front();
            q.push(j);
            xmx[i][j] = now[q.front()];
        }
        q.clear();
        for(int j = 1 ; j <= b ; ++j)
        {
            while(q.size() && now[j] < now[q.back()]) q.pop_back();
            while(q.size() && j - q.front() + 1 > n) q.pop_front();
            q.push(j);
            xmn[i][j] = now[q.front()];
        }
    }
    for(int j = 1 ; j <= b ; ++j)
    {
        q.clear();
        for(int i = 1 ; i <= a ; ++i)
        {
            while(q.size() && xmx[i][j] > xmx[q.back()][j]) q.pop_back();
            while(q.size() && i - q.front() + 1 > n) q.pop_front();
            q.push(i);
            f[i][j] = xmx[q.front()][j];
        }
    }
    for(int j = 1 ; j <= b ; ++j)
    {
        q.clear();
        for(int i = 1 ; i <= a ; ++i)
        {
            while(q.size() && xmn[i][j] < xmn[q.back()][j]) q.pop_back();
            while(q.size() && i - q.front() + 1 > n) q.pop_front();
            q.push(i);
            g[i][j] = xmn[q.front()][j];
        }
    }
//	for(int i = n ; i <= a ; ++i)
//		for(int j = n ; j <= b ; ++j)
//			printf("%d %d %d %d\n",i,j,f[i][j],g[i][j]);
}


int main()
{
    scanf("%d%d%d",&a,&b,&n);
    for(int i = 1 ; i <= a ; ++i)
        for(int j = 1 ; j <= b ; ++j)
            scanf("%d",&p[i][j]);
    solve();
    int ans  = 0x7fffffff;
    for(int i = n ; i <= a ; ++i)
        for(int j = n ; j <= b ; ++j)
            ans = std::min(ans , f[i][j] - g[i][j]);
    printf("%d\n",ans);
}

P2716 和谐的雪花

题目背景

没有背景

题目描述

现在有nm个雪花，被放在了一个nm的矩阵当中。每个雪花都有一个优美值。一个正方形的和谐度被定义为在这个正方形中雪花的最大优美值和最小优美值的差，和谐度越大这个正方形就越和谐。现在给出这个矩阵和一个非负整数k，zzs和zzy希望你能告诉他，在所有和谐度不小于k的正方形中，边长最小的正方形的边长（即找到一个最小的边长a，使得存在一个边长为a的正方形它的和谐度不小于k）。如果没有解，输出-1。

输入输出格式

输入格式：

第一行两个正整数和一个非负整数，n、m和k。

接下来n行，每行m个非负整数，表示题目中的矩阵。

输出格式：

如果有解，则输出一个正整数，表示答案。如果无解，则是-1。

输入输出样例

输入样例#1：

1
2
3
4
3 5 7
3 4 2 8 7
6 5 2 4 6
3 1 4 0 9

输出样例#1：

1
2

说明

对于20%的数据，1<=n,m<=20；

对于100%的数据，1<=n,m<=500；

对于100%的数据，矩阵中所有数不超过100000。

题解

上面那个套个二分即可解决。。

至于为什么答案单调？一个更大的正方形的极值之差必定比它包含的正方形要打，更容易满足条件，因此可以二分

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 1005
int a , b , n ,  p[maxn][maxn] , f[maxn][maxn] , g[maxn][maxn] , xmx[maxn][maxn] , xmn[maxn][maxn];

struct Deque 
{
	int l , r , q[maxn];
	Deque(){
		l = 1 , r = 0;
	//	std::memset(q,0,sizeof(q));
	}
	void clear(){
		l = 1 , r = 0;
	//	std::memset(q,0,sizeof(q));
	}
	void push(int x){
		q[++r] = x;
	}
	int size(){
		return r-l+1;
	}
	int front(){
		return q[l];
	}
	int back(){
		return q[r];
	}
	void pop_back(){
		q[r--] = 0;
	}
	void pop_front(){
		q[l++] = 0;
	}
}q;

inline void solve(int n)
{
	for(int i = 1 ; i <= a ; ++i)
	{
		q.clear();
		int* now = p[i];
		for(int j = 1 ; j <= b ; ++j)
		{
			while(q.size() && now[j] > now[q.back()]) q.pop_back();
			while(q.size() && j - q.front() + 1 > n) q.pop_front();
			q.push(j);
			xmx[i][j] = now[q.front()];
		}
		q.clear();
		for(int j = 1 ; j <= b ; ++j)
		{
			while(q.size() && now[j] < now[q.back()]) q.pop_back();
			while(q.size() && j - q.front() + 1 > n) q.pop_front();
			q.push(j);
			xmn[i][j] = now[q.front()];
		}
	}
	for(int j = 1 ; j <= b ; ++j)
	{
		q.clear();
		for(int i = 1 ; i <= a ; ++i)
		{
			while(q.size() && xmx[i][j] > xmx[q.back()][j]) q.pop_back();
			while(q.size() && i - q.front() + 1 > n) q.pop_front();
			q.push(i);
			f[i][j] = xmx[q.front()][j];
		}
	}
	for(int j = 1 ; j <= b ; ++j)
	{
		q.clear();
		for(int i = 1 ; i <= a ; ++i)
		{
			while(q.size() && xmn[i][j] < xmn[q.back()][j]) q.pop_back();
			while(q.size() && i - q.front() + 1 > n) q.pop_front();
			q.push(i);
			g[i][j] = xmn[q.front()][j];
		}
	}
//	for(int i = n ; i <= a ; ++i)
//		for(int j = n ; j <= b ; ++j)
//			printf("%d %d %d %d\n",i,j,f[i][j],g[i][j]);
}

inline bool check(int k)
{
	std::memset(xmx,0,sizeof(xmx));
	std::memset(xmn,0,sizeof(xmn));
	std::memset(f,0,sizeof(f));
	std::memset(g,0,sizeof(g));
	solve(k);
	int ans  = -0x7fffffff;
	for(int i = k ; i <= a ; ++i)
		for(int j = k ; j <= b ; ++j)
			ans = std::max(ans , f[i][j] - g[i][j]);
	if(ans >= n) return true;
	else return false;
}



int main()
{
	scanf("%d%d%d",&a,&b,&n);
	for(int i = 1 ; i <= a ; ++i)
		for(int j = 1 ; j <= b ; ++j)
			scanf("%d",&p[i][j]);
	int l = 1 , r = std::min(a,b) , ans = -1;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) ans = mid , r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
}