CodeForces 873C(贪心)

深藏阁楼爱情的钟 2022-06-07 12:49 126阅读 0赞

问题描述:

Ivan is playing a strange game.

He has a matrix a with n rows and m columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1\-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows:

1.  Initially Ivan's score is 0;
2.  In each column, Ivan will find the topmost 1 (that is, if the current column is j, then he will find minimum i such that ai, j = 1). If there are no 1's in the column, this column is skipped;
3.  Ivan will look at the next min(k, n - i + 1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score.

Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score.

Input

The first line contains three integer numbers n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100).

Then n lines follow, i\-th of them contains m integer numbers — the elements of i\-th row of matrix a. Each number is either 0 or 1.

Output

Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score.

Example

Input

4 3 2
    0 1 0
    1 0 1
    0 1 0
    1 1 1

Output

4 1

Input

3 2 1
    1 0
    0 1
    0 0

Output

2 0

题目题意:给我们一个n\*m的矩阵，让我们求出这个矩阵的最大可能的“值”，矩阵的值等于矩阵每一列连续区间长度为K中1的个数（其中这个区间的开头必须是1）的和。我们还有一个操作就是把任意的1变成0，问最大值和最小变换次数。

题目分析:我们遍历每一列求出连续区间的最多1的个数，然后查询这个区间是这一列的第几个区间，那么这一列的最小变换次数就是这个数

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    int a[205][205];
    int n,m,k;
    int fun(int x,int y)
    {
        int sum=0;
        for (int i=x;i<=x+k-1;i++)//连续区间1的个数
            sum+=a[i][y];
        return sum;
    }
    
    int main()
    {
        scanf("%d%d%d",&n,&m,&k);
        memset (a,0,sizeof (a));
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                scanf("%d",&a[i][j]);
            }
        }
        int sum=0,cnt=0;
        for (int j=1;j<=m;j++) {
            int res=0,cur=0;
            for (int i=1;i<=n;i++) {
                if (a[i][j]){//求出这列的最大值
                    cur=max(cur,fun(i,j));
                }
            }
            for (int i=1;i<=n;i++) {//查询这一列
                if (a[i][j]){
                    if ((fun(i,j)==cur)) {
                        break;
                    }
                    res++;
                }
            }
            sum+=cur;
            cnt+=res;
        }
        printf("%d %d\n",sum,cnt);
    
        return 0;
    }