| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 658847 | Shahrad | T-Covering (eJOI19_covering) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; #define endl '\n' #define pb push_back #define mk make_pair #define sz size() #define F first #define S second #define all(x) x.begin(), x.end() #define kill(x) return cout << x << endl, void(); #define int ll typedef pair <int, int> pii; #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") const int N = 1e6 + 5; const int MOD = 998244353, INF = 2e9, MOD2 = 1e9 + 7, sq = 350; int dx[8] = {0, 1, 0, -1, -1, -1, 1, 1}, dy[8] = {-1, 0, 1, 0, -1, 1, 1, -1}, vis[N]; vector <int> a[N], mrk[N], adj[N]; int ans, mn, few, n, m; bool val (int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; } void wef (int x, int y, int q) { ans += a[x][y]; mrk[x][y] = 0; a[x][y] = -INF; for (int i = 0; i < 4; i++) { if (dx[i] == dx[q]) continue; if (!val (x + dx[i], y + dy[i])) { ans += -INF; continue; } ans += a[x + dx[i]][y + dy[i]]; a[x + dx[i]][y + dy[i]] = -INF; } } void dfs (int v, int par) { vis[v] = 1; int x = v / m, y = v % m; for (int i = 0; i < 4; i++) { if (val (x + dx[i], y + dy[i])) mn = min (mn, a[x + dx[i]][y + dy[i]]); else mn = -INF; } for (int u : adj[v]) { if (u != par && !vis[u]) dfs (u, v); else if (u != par) few++; } } void Solve () { int k, x, y; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> x; a[i].pb (x); mrk[i].pb (0); } cin >> k; for (int i = 0; i < k; i++) { cin >> x >> y; mrk[x][y] = 1; } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int q = 0; q < 8; q++) if (val (i + dx[q], j + dy[q]) && mrk[i][j] && mrk[i + dx[q]][j + dy[q]]) { wef (i, j, q); wef (i + dx[q], j + dy[q], (q + 2) % 4 + (q > 3 ? 4 : 0)); } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (!mrk[i][j]) continue; ans += a[i][j]; for (int q = 0; q < 4; q++) { if (val (i + dx[q], j + dy[q])) ans += a[i + dx[q]][j + dy[q]]; else ans += -INF; } if (val (i + 2, j) && mrk[i + 2][j]) { int v = i * m + j, u = (i + 2) * m + j; ans -= a[i + 1][j]; adj[v].pb (u); adj[u].pb (v); } if (val (i, j + 2) && mrk[i][j + 2]) { int v = i * m + j, u = i * m + j + 2; ans -= a[i][j + 1]; adj[v].pb (u); adj[u].pb (v); } } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (!mrk[i][j]) continue; int v = i * m + j; if (vis[v]) continue; mn = INF, few = 0; dfs (v, -1);few/=2; if (few > 1) kill ("No"); if (few == 0) ans -= mn; } if (ans < 0) kill ("No"); cout << ans << endl; } int32_t main () { ios::sync_with_stdio (0), cin.tie (0), cout.tie (0); int tt = 1; // cin >> tt; while (tt--) Solve (); }