#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
int N, M, K, B, Z;
vector<vector<int> > dist;
bool inRange(int i, int j){
return 0 <= i && i < N && 0 <= j && j < M;
}
int cnt[1000003];
int backup[1000003];
int main() {
cin >> N >> M >> K >> B >> Z;
dist = vector<vector<int> >(N, vector<int>(M, -1));
queue<pair<int,int> > q;
for(int i = 0 ; i < K; i++){
int r,c;
cin >> r >> c;
r--, c--;
q.push({r, c});
dist[r][c] = 0;
}
int maxD = 0;
while(!q.empty()){
auto p = q.front();
q.pop();
int ci = p.first;
int cj = p.second;
for(int k = 0 ; k < 4; k++){
int ni = ci + "1021"[k] - '1';
int nj = cj + "0112"[k] - '1';
if(!inRange(ni, nj) || dist[ni][nj] != -1) continue;
dist[ni][nj] = dist[ci][cj] + 1;
cnt[dist[ni][nj]]++;
maxD = max(maxD, dist[ni][nj]);
q.push({ni, nj});
}
}
for(int i = 0; i <= maxD; i++) backup[i] = cnt[i];
int ans1 = 0;
int t = 0;
int cur = Z;
for(int i = maxD; t < i;) {
if(cnt[i] > cur){
cnt[i] -= cur;
ans1 += cur;
cur = Z;
t++;
}
else {
cur -= cnt[i];
ans1 += cnt[i];
i--;
}
}
cout << ans1 << endl;
for(int i = 0 ; i <= maxD; i++) cnt[i] = backup[i];
int ans2 = 0;
t = 0;
int pos = 1;
cur = Z;
while(t < maxD && pos <= maxD) {
if(t == pos) pos = t + 1;
if(cnt[pos] > cur){
cnt[pos] -= cur;
ans2 += cur;
cur = Z;
t++;
}
else {
cur -= cnt[pos];
ans2 += cnt[pos];
pos++;
}
}
cout << ans2;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
9836 KB |
Output is correct |
2 |
Correct |
0 ms |
9836 KB |
Output is correct |
3 |
Correct |
33 ms |
13796 KB |
Output is correct |
4 |
Correct |
33 ms |
13820 KB |
Output is correct |
5 |
Correct |
33 ms |
13780 KB |
Output is correct |
6 |
Correct |
26 ms |
16932 KB |
Output is correct |
7 |
Correct |
33 ms |
13820 KB |
Output is correct |
8 |
Correct |
26 ms |
17652 KB |
Output is correct |
9 |
Correct |
86 ms |
64560 KB |
Output is correct |
10 |
Correct |
33 ms |
13796 KB |
Output is correct |
11 |
Correct |
36 ms |
13952 KB |
Output is correct |
12 |
Correct |
36 ms |
13780 KB |
Output is correct |
13 |
Correct |
36 ms |
16932 KB |
Output is correct |
14 |
Correct |
29 ms |
13820 KB |
Output is correct |
15 |
Correct |
29 ms |
17652 KB |
Output is correct |
16 |
Correct |
143 ms |
64560 KB |
Output is correct |
17 |
Correct |
49 ms |
14060 KB |
Output is correct |
18 |
Correct |
66 ms |
14480 KB |
Output is correct |
19 |
Correct |
49 ms |
14044 KB |
Output is correct |
20 |
Correct |
46 ms |
17064 KB |
Output is correct |
21 |
Correct |
69 ms |
14744 KB |
Output is correct |
22 |
Correct |
36 ms |
17652 KB |
Output is correct |
23 |
Correct |
253 ms |
64560 KB |
Output is correct |
24 |
Correct |
769 ms |
22176 KB |
Output is correct |
25 |
Correct |
753 ms |
22128 KB |
Output is correct |
26 |
Correct |
799 ms |
22156 KB |
Output is correct |
27 |
Correct |
989 ms |
25220 KB |
Output is correct |
28 |
Correct |
789 ms |
22100 KB |
Output is correct |
29 |
Correct |
753 ms |
22004 KB |
Output is correct |
30 |
Memory limit exceeded |
159 ms |
65536 KB |
Memory limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |