Submission #1221599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221599		khome	T-Covering (eJOI19_covering)	C++20	0 / 100	10 ms	24392 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define intl long long

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int>> els(n, vector<int>(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> els[i][j];
        }
    }
    
    int k; cin >> k;
    vector<pair<int, int>> xs(k);
    for (int i = 0; i < k; i ++){
        int x, y; cin >> x >> y;
        xs[i] = {x, y};
    }
    sort(xs.begin(), xs.end());
    bool so = true;
    vector<set<pair<int, int>>> components;
    
    for (auto& pr : xs){
        int x = pr.first, y = pr.second;
        bool est = false;

        for (set<pair<int, int>> &st : components){
            if (st.find({x-1, y-1}) != st.end()) est = true;
            
            else if (st.find({x+1, y+1}) != st.end()) est = true;
            
            else if (st.find({x-1, y}) != st.end()) est = true;

            else if (st.find({x, y-1}) != st.end()) est = true;

            else if (st.find({x+1, y}) != st.end()) est = true;

            else if (st.find({x, y+1}) != st.end()) est = true;

            else if (st.find({x, y+2}) != st.end()) est = true;

            else if (st.find({x, y-2}) != st.end()) est = true;

            else if (st.find({x+2, y}) != st.end()) est = true;

            else if (st.find({x-2, y}) != st.end()) est = true;

            if (est) {
                st.insert({x, y});
                break;
            }
        }

        if (!est) {
            components.push_back({{x, y}});
        }
    }
    
    int ans = 0;
    for (auto smth : components){
        set<vector<int>> sosedi;
        int cnt = 0;
        for (pair<int, int> pr : smth) {
            int x = pr.first, y = pr.second;
            cnt += els[x][y];

            if (x-1 >= 0 && sosedi.find({els[x-1][y], x-1, y}) == sosedi.end()) {
                sosedi.insert({els[x-1][y], x-1, y}); 
                cnt += els[x-1][y];
            }

            if (x+1 < n && sosedi.find({els[x+1][y], x+1, y}) == sosedi.end()) {
                sosedi.insert({els[x+1][y], x+1, y}); 
                cnt += els[x+1][y];
            }

            if (y-1 >= 0 && sosedi.find({els[x][y-1], x, y-1}) == sosedi.end()) {
                sosedi.insert({els[x][y-1], x, y-1}); 
                cnt += els[x][y-1];
            }

            if (y+1 < m && sosedi.find({els[x][y+1], x, y+1}) == sosedi.end()) {
                sosedi.insert({els[x][y+1], x, y+1}); 
                cnt += els[x][y+1];
            }

        }

        if (sosedi.size() < 3*smth.size()) {cout << "No" << endl; return;}

        if (sosedi.size() == 3*smth.size()) ans += cnt;

        if (sosedi.size() == 3*smth.size() + 1) ans += cnt - (*sosedi.begin())[0];
    }
    cout << ans << endl;
    // cout << "YYAY" << endl;

}

signed main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	int t = 1; 
    // cin >> t;
    while (t--)solve();
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
covering.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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