UVa/uva-10360.cpp at master · debugster/UVa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>

using namespace std;

/* typedef starts */

typedef long long ll;
typedef unsigned long long ull;

/* typedef ends */

/* macro starts */

#define PI acos(-1.0)
#define MAX 1025

/* macro ends */

/* function starts */

/// calculates n-th (0-based) Gray Code
template<typename dataType>
dataType nthGrayCode(dataType n)
{
    return (n ^ (n >> 1));
}

/// generates all possible subsets for the given set
template<typename dataType>
void generateAllSubset(vector<dataType> &data)
{
    int i, j, n;
    n = data.size();

    for (i = 0; i < (1 << n); i++) {
        for (j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cout << data[j] << " ";
            }
        }
        cout << "\n";
    }
}

/* function ends */

int killed[MAX][MAX];

struct NODE
{
    int x;
    int y;
    int s;
};

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

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int test, d, n, i, j, k, x, y, s, ans;
    vector<NODE>all;

    cin >> test;
    while (test--) {
        cin >> d >> n;
        all.clear();
        for (i = 0; i < n; i++) {
            cin >> x >> y >> s;
            all.push_back({x, y, s});
        }

        for (i = 0; i < MAX; i++) {
            for (j = 0; j < MAX; j++) {
                killed[i][j] = 0;
            }
        }

        for (k = 0; k < n; k++) {
            x = all[k].x;
            y = all[k].y;
            s = all[k].s;

            for (i = x - d; i <= x + d; i++) {
                if (i < 0 || i >= MAX) {
                    continue;
                }
                for (j = y - d; j <= y + d; j++) {
                    if (j < 0 || j >= MAX) {
                        continue;
                    }

                    killed[i][j] += s;
                }
            }
        }

        ans = -1;
        for (i = 0; i < MAX; i++) {
            for (j = 0; j < MAX; j++) {
                if (killed[i][j] > ans) {
                    ans = killed[i][j];
                    x = i;
                    y = j;
                }
            }
        }

        cout << x << " " << y << " " << ans << "\n";
    }

    return 0;
}