ACM (TJU) : 1088


#include <cstdio>
#include <algorithm>
using namespace std;

struct node {
    int x;
    int y;
    int nut;
} a [2550];

bool cmp (node p, node q)
{
    return p.nut > q.nut;
}

int main ()
{
    int dataset;
    scanf ("%d", &dataset);

    while ( dataset-- ) {
        int m, n, k;
        scanf ("%d %d %d", &m, &n, &k);

        int field [52] [52];
        int index = 0;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                scanf ("%d", &field [i] [j]);

                if ( field [i] [j] ) {
                    a [index].nut = field [i] [j];
                    a [index].x = i;
                    a [index].y = j;
                    index++;
                }
            }
        }

        sort (a, a + index, cmp);

        int totalNut = 0;
        int cur_x = 0;
        int cur_y = a [0].y;
        k--;

        for ( int i = 0; i < index; i++ ) {
            int inCost = abs (cur_x - a [i].x) + abs (cur_y - a [i].y) + 1;
            int outCost = abs (0 - a [i].x) + 1;
            int tempCost = inCost + outCost;

            if ( tempCost <= k ) {
                k -= inCost;
                cur_x = a [i].x;
                cur_y = a [i].y;
                totalNut += a [i].nut;
            }

            else
                break;
        }

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

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s