[Link] https://www.acmicpc.net/problem/17143
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
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int MAX = 5e5 + 1;
const int INF = 987654321;
int r, c, m;
struct shark {
int speed, dir, size, idx;
int i, j;
bool caught = false;
shark(int i, int j, int speed, int dir, int size, int idx):
i(i), j(j), speed(speed), dir(dir), size(size), idx(idx) {}
};
vector<shark> sharks;
vector<int> idx_map;
int mm[100][100];
int tmp[100][100];
bool cmp(shark l, shark r) {
return l.size < r.size;
}
void solve() {
int pos = -1, fish_sum= 0;
for0(iter, c) {
pos++;
for0(i, r) {
if(mm[i][pos]) {
sharks[idx_map[mm[i][pos]]].caught= true;
fish_sum += sharks[idx_map[mm[i][pos]]].size;
mm[i][pos] = 0;
break;
}
}
for0(i, m) {
if(sharks[i].caught) continue;
if(sharks[i].dir == 1 || sharks[i].dir == 2) {
int ai = sharks[i].i + (sharks[i].dir == 1 ? -1 : 1) * sharks[i].speed, aj = sharks[i].j;
bool dir_change = false;
while(true) {
if(0 <= ai && ai < r) break;
if(ai < 0) ai *= -1;
else ai = 2*(r-1) - ai;
dir_change = !dir_change;
}
if(dir_change) sharks[i].dir = sharks[i].dir == 1 ? 2 : 1;
if(tmp[ai][aj] && idx_map[tmp[ai][aj]] < i) sharks[idx_map[tmp[ai][aj]]].caught = true;
tmp[ai][aj] = sharks[i].idx;
sharks[i].i = ai;
}
else if(sharks[i].dir == 3 || sharks[i].dir == 4) {
int ai = sharks[i].i, aj = sharks[i].j + (sharks[i].dir == 3 ? 1 : -1) * sharks[i].speed;
bool dir_change = false;
while(true) {
if(0 <= aj && aj < c) break;
if(aj < 0) aj *= -1;
else aj = 2*(c-1) - aj;
dir_change = !dir_change;
}
if(dir_change) sharks[i].dir = sharks[i].dir == 3 ? 4 : 3;
if(tmp[ai][aj] && idx_map[tmp[ai][aj]] < i) sharks[idx_map[tmp[ai][aj]]].caught = true;
tmp[ai][aj] = sharks[i].idx;
sharks[i].j = aj;
}
}
for0(i, r) for0(j, c) {
mm[i][j] = tmp[i][j], tmp[i][j] = 0;
}
}
cout << fish_sum;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c >> m;
idx_map.resize(m + 1);
for0(i, m) {
int r, c, s, d, z; cin >> r >> c >> s >> d >> z;
r--, c--;
sharks.push_back(shark(r, c, s, d, z, i+1));
mm[r][c] = i+1;
}
sort(sharks.begin(), sharks.end(), cmp);
for0(i, m) { idx_map[sharks[i].idx] = i; }
solve();
return 0;
}