제출 #647905

#제출 시각아이디문제언어결과실행 시간메모리
6479051zaid1T-Covering (eJOI19_covering)C++17
15 / 100
66 ms24200 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define double long double #define F first #define S second const int M = 3e3+5; vector<int> node[M]; int vis[M], dp[M][4]; vector<vector<int>> ar, x, buff; vector<pair<int, int>> v={{0,0}}, p = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; void dfs(int s) { vis[s] = true; vector<int> z; for (int i:node[s]) { if (!vis[i]) { z.push_back(i); dfs(i); } } for (auto [dx, dy]:p) buff[v[s].F+dx][v[s].S+dy]++; for (int a = 0; a < 4; a++) { buff[v[s].F+p[a].F][v[s].S+p[a].S]--; for (auto u:z) { if (dp[s][a] < 0) break; for (auto [dx, dy]:p) buff[v[u].F+dx][v[u].S+dy]++; int mx = -1; for (int b = 0; b < 4; b++) { if (dp[u][b] < 0) continue; buff[v[u].F+p[b].F][v[u].S+p[b].S]--; bool ok = true; for (auto [dx, dy]:p) { if (buff[v[u].F+dx][v[u].S+dy] == 2 || buff[v[s].F+dx][v[s].S+dy] == 2) { ok = false; break; } } if (ok) { mx = max(mx, dp[u][b]); } buff[v[u].F+p[b].F][v[u].S+p[b].S]++; } if (mx >= 0) dp[s][a] += mx; else dp[s][a] = mx; for (auto [dx, dy]:p) buff[v[u].F+dx][v[u].S+dy]--; } if (dp[s][a] >= 0) { for (auto [dx, dy]:p) dp[s][a] += ar[v[s].F+dx][v[s].S+dy]; dp[s][a] += ar[v[s].F][v[s].S]-ar[v[s].F+p[a].F][v[s].S+p[a].S]; } buff[v[s].F+p[a].F][v[s].S+p[a].S]++; } for (auto [dx, dy]:p) buff[v[s].F+dx][v[s].S+dy]--; } signed main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; x = vector<vector<int>>(n+5, vector<int>(m+5, 0)); ar = vector<vector<int>>(n+5, vector<int>(m+5, 0)); buff = vector<vector<int>>(n+5, vector<int>(m+5, 0)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> ar[i][j]; int k; cin >> k; for (int i = 1; i <= k; i++) { int a, b; cin >> a >> b; a++;b++; x[a][b] = i; v.push_back({a, b}); } for (auto [a, b]:v) { for (int i = a-2; i <= a+2; i++) { for (int j = b-2; j <= b+2; j++) { if (i == a && j == b || i < 1 || j < 1 || i > n || j > m || !x[i][j]) continue; node[x[a][b]].push_back(x[i][j]); } } } int ans = 0; for (int i = 1; i <= k; i++) { if (!vis[i]) { dfs(i); if (*max_element(dp[i], dp[i]+4) == -1) { cout << "No" << endl; return 0; } ans += *max_element(dp[i], dp[i]+4); } } // for (int i = 1; i <= k; i++) { // cout << i << ": "; // for (auto j:dp[i]) cout << j << ' '; cout << endl; // } cout << ans << endl; return 0; } /* 5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 4 5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 3 */

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'int main()':
covering.cpp:94:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |                 if (i == a && j == b || i < 1 || j < 1 || i > n || j > m || !x[i][j]) continue;
      |                     ~~~~~~~^~~~~~~~~
#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...