#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false)
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;
map<pair<int,int>, int> dist;
bool inRange(int i, int j){
return 0 <= i && i < N && 0 <= j && j < M;
}
int cnt[2000003];
int backup[2000003];
int main() {
fastio();
cin >> N >> M >> K >> B >> Z;
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[make_pair(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.find(make_pair(ni, nj)) != dist.end()) continue;
int d = dist[make_pair(ni, nj)] = dist[make_pair(ci, cj)] + 1;
cnt[d]++;
maxD = max(maxD, d);
q.push(make_pair(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 |
17808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17940 KB |
Output is correct |
| 3 |
Execution timed out |
1000 ms |
65536 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
