UVa 10360 - Rat Attack



#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <stdio.h>
#include <math.h>
typedef std::vector<int> vi;
using namespace std;
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

int main() {
	int t;
	static int killed[1025][1025];
	cin >>t;
	while(t--){
		int d, n, x, y, sz, max=0;
		cin >>d>>n;
		fill_n(&killed[0][0], 1025*1025,0);
		while(n--){
			cin >> x >>y>>sz;
			for(int X=max(0, x-d);X<=min(x+d, 1024);X++)
				for(int Y=max(0, y-d);Y<=min(y+d, 1024);Y++)
					killed[X][Y]+=sz;
		}
		for(int X=0;X<1025;X++)
				for(int Y=0;Y<1025;Y++)
					if(killed[X][Y]>max){
						max=killed[X][Y];
						x=X;y=Y;
					}
		cout<<x<<" "<<y<<" "<<max<<endl;

	}
	return 0;
}
Runtime:0.092
Ideone: http://ideone.com/psjIWM

Comments

Popular Posts