제출 #951824

#제출 시각아이디문제언어결과실행 시간메모리
951824EJIC_B_KEDAXT-Covering (eJOI19_covering)C++17
100 / 100
222 ms27792 KiB
#include <bits/stdc++.h> #include <random> #ifndef LOCAL //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; typedef long long ll; typedef double dd; typedef long double ld; typedef unsigned int uii; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void solve(); mt19937_64 mt(1); int32_t main() { #ifdef LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen("amusing.in", "r", stdin); //freopen("amusing.out", "w", stdout); #endif cout << fixed << setprecision(30); int tests = 1; //cin >> tests; while (tests--) { solve(); } } pair<int, int> to[8] = {{2, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}, p[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; bool check(int i, int j, pair<int, int> s, vector<vector<int>>& a, vector<vector<int>>& used) { return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y]; } void dfs(int i, int j, vector<vector<int>>& a, vector<vector<int>>& used, multiset<int>& st, int& sz, int& sum) { used[i][j] = 1; sz++; sum += a[i][j]; for (auto s : p) { if (check(i, j, s, a, used)) { st.insert(a[i + s.x][j + s.y]); used[i + s.x][j + s.y] = 1; sum += a[i + s.x][j + s.y]; } } for (auto s : to) { if (check(i, j, s, a, used)) { dfs(i + s.x, j + s.y, a, used, st, sz, sum); } } } void solve() { int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)), used(n, vector<int>(m, 0)); int sz = 0, sum = 0; multiset<int> st; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; if (!((i + j) % 2)) { used[i][j] = 1; } } } int k; cin >> k; ll res = 0; vector<pair<int, int>> points(k); for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; points[i] = {x, y}; } for (int i = 0; i < k; i++) { used[points[i].x][points[i].y] = !used[points[i].x][points[i].y]; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!((i + j) % 2) && !used[i][j]) { dfs(i, j, a, used, st, sz, sum); if (3 * sz > st.size()) { cout << "No\n"; return; } while (3 * sz != st.size()) { sum -= *st.begin(); st.erase(st.begin()); } res += sum; sz = 0; sum = 0; st.clear(); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i + j) % 2) { used[i][j] = 1; } else { used[i][j] = 0; } } } for (int i = 0; i < k; i++) { used[points[i].x][points[i].y] = !used[points[i].x][points[i].y]; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i + j) % 2 && !used[i][j]) { dfs(i, j, a, used, st, sz, sum); if (3 * sz > st.size()) { cout << "No\n"; return; } while (3 * sz != st.size()) { sum -= *st.begin(); st.erase(st.begin()); } res += sum; sz = 0; sum = 0; st.clear(); } } } cout << res << '\n'; }

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

covering.cpp: In function 'bool check(int, int, std::pair<int, int>, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
covering.cpp:45:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y];
      |                            ~~~~~~~~^~~~~~~~~~
covering.cpp:45:74: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y];
      |                                                                  ~~~~~~~~^~~~~~~~~~~~~
covering.cpp: In function 'void solve()':
covering.cpp:96:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 if (3 * sz > st.size()) {
      |                     ~~~~~~~^~~~~~~~~~~
covering.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 while (3 * sz != st.size()) {
      |                        ~~~~~~~^~~~~~~~~~~~
covering.cpp:127:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                 if (3 * sz > st.size()) {
      |                     ~~~~~~~^~~~~~~~~~~
covering.cpp:131:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                 while (3 * sz != st.size()) {
      |                        ~~~~~~~^~~~~~~~~~~~
#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...