CodeForces 873C(욕심)

문제 설명:
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:

Initially Ivan's score is 0;

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;

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
#include
#include
#include
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
",sum,cnt);

    return 0;
}