Submission #456340

#TimeUsernameProblemLanguageResultExecution timeMemory
456340SamAndT-Covering (eJOI19_covering)C++17
100 / 100
260 ms26468 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 1000006; const int xx[4] = {0, 1, 0, -1}; const int yy[4] = {1, 0, -1, 0}; //const int cc[4] = {'R', 'D', 'L', 'U'}; int n, m; template <typename T> void bil(T**& a) { a = new T*[n + 5]; for (int i = 0; i < n + 5; ++i) a[i] = new T[m + 5]; for (int i = 0; i <= n + 1; ++i) { for (int j = 0; j <= m + 1; ++j) { a[i][j] = 0; } } } int** a; int k; bool** c; bool** cc; vector<pair<int, int> > v; void dfs(int x, int y) { cc[x][y] = true; v.push_back(m_p(x, y)); for (int i = 0; i < 4; ++i) { int hx = x + xx[i] * 2; int hy = y + yy[i] * 2; if (1 <= hx && hx <= n && 1 <= hy && hy <= m) { if (c[hx][hy] && !cc[hx][hy]) { dfs(hx, hy); } } } } void solv() { cin >> n >> m; bil(a); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; } } cin >> k; bil(c); for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; ++x; ++y; c[x][y] = true; } int** u; bil(u); for (int i = 0; i <= n + 1; ++i) { for (int j = 0; j <= m + 1; ++j) { u[i][j] = -1; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (c[i][j] && c[i][j + 1]) { u[i][j] = 2; u[i][j + 1] = 0; } if (c[i][j] && c[i + 1][j]) { u[i][j] = 3; u[i + 1][j] = 1; } if (c[i][j] && c[i + 1][j + 1]) { u[i][j] = 2; u[i + 1][j + 1] = 0; } if (c[i][j] && c[i - 1][j + 1]) { u[i][j] = 2; u[i - 1][j + 1] = 0; } } } int** q; bil(q); for (int j = 0; j <= m; ++j) { q[0][j] = q[n + 1][j] = 1; } for (int i = 0; i <= n; ++i) { q[i][0] = q[i][m + 1] = 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (u[i][j] != -1) { c[i][j] = false; ++q[i][j]; for (int d = -1; d <= 1; ++d) ++q[i + xx[(u[i][j] + d + 4) % 4]][j + yy[(u[i][j] + d + 4) % 4]]; } } } for (int i = 0; i <= n + 1; ++i) { for (int j = 0; j <= m + 1; ++j) { if (q[i][j] > 1) { cout << "No\n"; return; } } } int ans = 0; bil(cc); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (c[i][j] && !cc[i][j]) { v.clear(); dfs(i, j); set<pair<int, int> > s; for (int i = 0; i < sz(v); ++i) { ++q[v[i].fi][v[i].se]; for (int j = 0; j < 4; ++j) { if (!q[v[i].fi + xx[j]][v[i].se + yy[j]]) s.insert(m_p(v[i].fi + xx[j], v[i].se + yy[j])); } } if (sz(s) < sz(v) * 3) { cout << "No\n"; return; } if (sz(s) == sz(v) * 3) { for (auto it = s.begin(); it != s.end(); ++it) ans += a[it->fi][it->se]; } else { int minu = N; for (auto it = s.begin(); it != s.end(); ++it) { ans += a[it->fi][it->se]; minu = min(minu, a[it->fi][it->se]); } ans -= minu; } } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (q[i][j]) ans += a[i][j]; } } cout << ans << "\n"; } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solv(); } return 0; }
#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...