Cod sursa(job #300508)

Utilizator luckBogdan Luca luck Data 7 aprilie 2009 14:42:45
Problema Teren Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define t(i,j) *(t+(i)*m+j)

void showmat(int *t, int n, int m) {
    int i, j;
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++)
            printf("%3d", t(i, j));
        printf("\n");
    }
    printf("\n");
}

int main() {
    int n, m, x, i, j, v, k, amax, wmax, cl, cr, s, w;
    int *l;
    int *t;
    FILE *f;
    f = fopen("teren.in", "r");
    fscanf(f, "%d %d %d\n", &n, &m, &x);
    l = (int*)malloc(m * sizeof(int));
    t = (int*)malloc(m * n * sizeof(int));
    bzero(l, m * sizeof(int));
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++) {
            fscanf(f, "%d", &v);
            l[j] += v;
            t(i, j) = l[j];
        }
    fclose(f);
    /*showmat(t, n, m);*/
    amax = 0;
    for(i = 0; i < n; i++)
        for(j = i; j < n; j++) {
            for(k = 0; k < m; k++) {
                v = t(j, k);
                if(i > 0)
                    v -= t(i - 1, k);
                l[k] = v;
            }
            cl = cr = wmax = 0;
            s = 0;
            while(cr < m) {
                while(cr < m) {
                    s += l[cr++];
                    if(s > x)
                        break;
                }
                w = cr - cl;
                if(s > x)
                    w--;
                if(w > wmax)
                    wmax = w;
                while(cl < m && s > x)
                    s -= l[cl++];
            }
            if((j - i + 1) * wmax > amax)
                amax = (j - i + 1) * wmax;
            printf("%d %d: max is %d\n", i, j, wmax);
        }
    f = fopen("teren.out", "w");
    fprintf(f, "%d", amax);
    fclose(f);
    /*printf("%d\n", amax);*/
    return 0;
}