제출 #919335

#제출 시각아이디문제언어결과실행 시간메모리
919335raphaelpT-Covering (eJOI19_covering)C++14
55 / 100
171 ms16176 KiB
#include <bits/stdc++.h> using namespace std; void place(long long x, long long y, vector<vector<long long>> &special, long long &p, vector<long long> &depX, vector<long long> &depY, long long N, long long M, long long &tot, vector<vector<long long>> &Tab, long long &minn, int depth) { if (special[x][y] == 2) return; if (special[x][y] == 3) { p = 0; return; } tot += Tab[x][y]; long long choose = -1; for (long long j = 0; j < 4; j++) { if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M) { if (choose != -1) p = 0; choose = j; } else { minn = min(minn, Tab[x + depX[j]][y + depY[j]]); tot += Tab[x + depX[j]][y + depY[j]]; if (special[x + depX[j]][y + depY[j]] > 0) { if (choose != -1) p = 0; choose = j; } } } for (long long j = 4; j < 8; j++) { if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M) continue; if (special[x + depX[j]][y + depY[j]] == 1) { if (choose != -1) p = 0; choose = j - 4; } } if (p == 0) return; for (long long j = 0; j < 4; j++) { if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M) continue; if (j == choose) { tot -= Tab[x + depX[j]][y + depY[j]]; } else if (choose != -1) special[x + depX[j]][y + depY[j]] = 3; } special[x][y] = 2; if (choose != -1) return; special[x][y] = 4; for (long long j = 8; j < 12; j++) { if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M) continue; if (special[x + depX[j]][y + depY[j]] == 1) { place(x + depX[j], y + depY[j], special, p, depX, depY, N, M, tot, Tab, minn, depth + 1); } if (special[x + depX[j]][y + depY[j]] == 4) { tot -= Tab[x + depX[j - 8]][y + depY[j - 8]]; } if (special[x + depX[j - 8]][y + depY[j - 8]] == 3) { for (long long k = 0; k < 4; k++) { if (x + depX[k] < 0 || x + depX[k] >= N || y + depY[k] < 0 || y + depY[k] >= M) continue; special[x + depX[k]][y + depY[k]] = 3; } return; } } special[x][y] = 2; if (choose == -1 && depth == 0) tot -= minn; } int main() { long long N, M; cin >> N >> M; vector<vector<long long>> Tab(N, vector<long long>(M)); for (long long i = 0; i < N; i++) { for (long long j = 0; j < M; j++) { cin >> Tab[i][j]; } } long long K; cin >> K; vector<vector<long long>> special(N, vector<long long>(M)); vector<pair<long long, long long>> S; for (long long i = 0; i < K; i++) { long long a, b; cin >> a >> b; S.push_back({a, b}); special[a][b] = 1; } long long p = 1, tot = 0; vector<long long> depX = {0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2}, depY = {-1, 0, 1, 0, -1, 1, 1, -1, -2, 0, 2, 0}; for (long long i = 0; i < K; i++) { long long x = S[i].first; long long y = S[i].second; long long minn = 1000000; place(x, y, special, p, depX, depY, N, M, tot, Tab, minn, 0); if (p == 0) break; } if (p) cout << tot; else cout << "No"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...