2015年1月1日 星期四

USACO 2014 March Contest, Silver Problem 2. The Lazy Cow

/*
    把座標換成
    s = x+y+1
    r = x+y+N
    接著做 二維BIT
*/
// http://www.usaco.org/index.php?page=viewproblem2&cpid=416
#include <iostream>
#include <cstdio>

using namespace std;

int BIT[1000][1000] = {0};

int N, K;

void add(int _x, int _y, int num)
{
    int x, y;

    x = _x;
    while( x <= 2*N )
    {
        y = _y;
        while( y <= 2*N )
        {
            BIT[x][y] += num;
            y += y&-y;
        }

        x += x&-x;
    }
}

int ask(int _x, int _y)
{
    int x, y;
    int re = 0;

    x = min(_x, N*2);
    while( x > 0 )
    {
        y = min(_y, N*2);
        while( y > 0 )
        {
            re += BIT[x][y];
            y -= y&-y;
        }

        x -= x&-x;
    }

    return re;
}

int G[500][500];

int Ans = 0;

int main()
{
    freopen("lazy.in", "r", stdin);
    freopen("lazy.out", "w", stdout);

    scanf("%d %d", &N, &K);

    for(int Ni = 0; Ni < N; Ni++)
        for(int Nj = 0; Nj < N; Nj++)
        {
            scanf("%d", &G[Ni][Nj]);
            add(Ni+Nj+1, Ni-Nj+N, G[Ni][Nj]);
        }

    for(int Ni = 0; Ni < N; Ni++)
        for(int Nj = 0; Nj < N; Nj++)
        {
            int x = Ni+Nj+1;
            int y = Ni-Nj+N;

            int p = ask(x+K, y+K)-ask(x-K-1, y+K)-ask(x+K, y-K-1)+ask(x-K-1, y-K-1);
            Ans = max(Ans, p);
        }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言