Poj Solution 1916

http://poj.org/problem?id=1916

#include <iostream>
#include <string.h>
using namespace std;

int a[1030][1030];
int main()
{
    int test,d,n,i,max,j,temp,x,y,now;
    cin>>test;
    while(test--)
    {
        cin>>d;
        cin>>n;
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)
        {
            cin>>x>>y;
            cin>>a[x][y];
        }
        max=-1;
        for(i=1;i<1025;i++)
        {
            a[i][0]+=a[i-1][0];
            a[0][i]+=a[0][i-1];
        }
        temp=2*d+1;
        for(i=1;i<1025;i++)
            for(j=1;j<1025;j++) {
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
                if(i>=temp&&j>=temp) {
                    now=a[i][j]-a[i-temp][j]-a[i][j-temp]+a[i-temp][j-temp];
                    if(now>max) {
                        max=now;
                        x=i-d;
                        y=j-d;
                    }
                }
            }
        cout<<x<<" "<<y<<" "<<max<<endl;
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *