# SGU-167 I-country

Time Limit: 750ms
Memory Limit: 64MB

## Description

According to top-secret A-country plans, I-country is divided into N*M equal squares, each square contains some oil resources. They want to occupy all the territory of I-country, but the UN (United Nations) will allow them to occupy only K squares. Of course, A-country want to get control over as many oil as possible, but, they will have to guard all their territory. So, they need their territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ).
You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.

## Input

On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). Next N lines contains M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.

## Output

On the first line of output, write string “Oil : X”, where integer number X — the maximal number of oil which can be controlled by A-country. Next you should output K pairs of numbers — coordinates of the squares which will be occupied by A-country. The first coordinate is number of row (top to bottom, starting from 1), second is number of column (left to right, starting from 1).

## Sample Input

2 3 4
10 20 30
40 2 3


## Sample Output

Oil : 100
1 1
1 2
1 3
2 1


## 解题思路

– 已经处理的行数
– 已经选出的格子数
– 当前行左端点位置（0为递增,1为递减）
– 当前行右端点位置
– 左端点单调性类型
– 右端点单调性类型

#### 1. 左边界递减，右边界递增

$$F[i, j, l, r, 1, 0] = \sum_{p=l}^{r} A[i, p] + F[i-1, 0, 0, 0, 1, 0]$$

$$F[i, j, l, r, 1, 0] = \sum_{p=l}^{r} A[i, p] + \max_{l \leq p \leq q \leq r} { F[i-1, j-(r-l+1), p, q, 1, 0] }$$

#### 2. 左边界递减，右边界递减

$$F[i, j, l, r, 1, 1] = \sum_{p=l}^{r} A[i, p] + \max_{l \leq p \leq r \leq q} { F[i-1, j-(r-l+1), p, q, 1, 0/1] }$$

#### 3. 左边界递增，右边界递增

$$F[i, j, l, r, 0, 0] = \sum_{p=l}^{r} A[i, p] + \max_{p \leq l \leq q \leq r} { F[i-1, j-(r-l+1), p, q, 0/1, 0] }$$

#### 4. 左边界递增，右边界递减

$$F[i, j, l, r, 0, 1] = \sum_{p=l}^{r} A[i, p] + \max_{p \leq l \leq r \leq q} { F[i-1, j-(r-l+1), p, q, 0/1, 0/1] }$$

#include
#include
#include
#include
#include
#include

using namespace std;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

char last_l[16][226][16][16][2][2];
char last_r[16][226][16][16][2][2];
char last_x[16][226][16][16][2][2];
char last_y[16][226][16][16][2][2];

int start_l, start_r, start_x, start_y;

int data[16][16];
int f[16][226][16][16][2][2];
int n, m, k;
int ans, start;

inline void search(int i, int j, int l, int r, int x, int y){

if(j == 0)
return;

int length = r - l + 1;
search(i-1, j-length, last_l[i][j][l][r][x][y], last_r[i][j][l][r][x][y], last_x[i][j][l][r][x][y], last_y[i][j][l][r][x][y]);

for(register int p=l; p<=r; p++)
printf("%d %d\n", i, p);
}

int main(){

for(register int i=1; i<=n; i++)
for(register int j=1; j<=m; j++)

for(register int i=1; i<=n; i++){
for(register int j=1; j<=k; j++){
for(register int l=1; l<=m; l++){
for(register int r=l; r<=m; r++){
int length = r-l+1;
int sum = 0;
for(register int k=l; k<=r; k++)
sum += data[i][k];
int maxn = 0;

if(j < length)
continue;

if(j == length)
f[i][j][l][r][1][0] = sum + f[i-1][0][0][0][1][0];
else{
for(register int p=l; p<=r; p++)
for(register int q=p; q<=r; q++)
if(f[i-1][j-length][p][q][1][0] > maxn){
maxn = f[i-1][j-length][p][q][1][0];
last_l[i][j][l][r][1][0] = p;
last_r[i][j][l][r][1][0] = q;
last_x[i][j][l][r][1][0] = 1;
last_y[i][j][l][r][1][0] = 0;
}
f[i][j][l][r][1][0] = sum + maxn;
}
maxn = 0;
for(register int p=l; p<=r; p++)
for(register int q=r; q<=m; q++)
for(register int y=0; y<=1; y++)
if(f[i-1][j-length][p][q][1][y] > maxn){
maxn = f[i-1][j-length][p][q][1][y];
last_l[i][j][l][r][1][1] = p;
last_r[i][j][l][r][1][1] = q;
last_x[i][j][l][r][1][1] = 1;
last_y[i][j][l][r][1][1] = y;
}
f[i][j][l][r][1][1] = sum + maxn;
maxn = 0;
for(register int p=1; p<=l; p++)
for(register int q=l; q<=r; q++)
for(register int x=0; x<=1; x++)
if(f[i-1][j-length][p][q][x][0] > maxn){
maxn = f[i-1][j-length][p][q][x][0];
last_l[i][j][l][r][0][0] = p;
last_r[i][j][l][r][0][0] = q;
last_x[i][j][l][r][0][0] = x;
last_y[i][j][l][r][0][0] = 0;
}
f[i][j][l][r][0][0] = sum + maxn;
maxn = 0;
for(register int p=1; p<=l; p++)
for(register int q=r; q<=m; q++)
for(register int x=0; x<=1; x++)
for(register int y=0; y<=1; y++)
if(f[i-1][j-length][p][q][x][y] > maxn){
maxn = f[i-1][j-length][p][q][x][y];
last_l[i][j][l][r][0][1] = p;
last_r[i][j][l][r][0][1] = q;
last_x[i][j][l][r][0][1] = x;
last_y[i][j][l][r][0][1] = y;
}

f[i][j][l][r][0][1] = sum + maxn;
}
}
}
}

for(register int i=1; i<=n; i++){
for(register int l=1; l<=m; l++){
for(register int r=l; r<=m; r++){
for(register int x=0; x<=1; x++){
for(register int y=0; y<=1; y++){
if(f[i][k][l][r][x][y] > ans){
ans = f[i][k][l][r][x][y];
start_l = l;
start_r = r;
start_x = x;
start_y = y;
start = i;
}
}
}
}
}
}

printf("Oil : %d\n", ans);
search(start, k, start_l, start_r, start_x, start_y);
return 0;
}