Submission #951824

#	Time	Username	Problem	Language	Result	Execution time	Memory
951824		EJIC_B_KEDAX	T-Covering (eJOI19_covering)	C++17	100 / 100	222 ms	27792 KiB

covering

#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';
}

Compilation message (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()) {
      |                        ~~~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30