Submission #441647

#	Time	Username	Problem	Language	Result	Execution time	Memory
441647		Agnimandur	T-Covering (eJOI19_covering)	C++17	0 / 100	57 ms	37856 KiB

covering

#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define REP(i,a) for (int i = 0; i < (a); i++)
#define add push_back
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
//const ll MOD = 1000000007LL;
const ll MOD = 998244353LL;



int ni() {
    int x; cin >> x;
    return x;
}
 
ll nl() {
    ll x; cin >> x;
    return x;
}
 
double nd() {
    double x; cin >> x;
    return x;
}
 
string next() {
    string x; cin >> x;
    return x;
}


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    vector<vi> dirs;
    vector<vi> dirs1;
    for (int x = -2; x <= 2; x++) {
        for (int y = -2; y <= 2; y++) {
            int d = abs(x)+abs(y);
            if (0<d&&d<=2) {
                vi dir = {x,y};
                dirs.add(dir);
            }
            if (0<d&&d<=1) {
                vi dir = {x,y};
                dirs1.add(dir);
            }
        }
    }

    int ans = 0;


    int N = ni();
    int M = ni();
    vector<vi> grid(N,vi(M,0));
    vector<vi> occ(N,vi(M,0));

    REP(i,N) REP(j,M) {
        grid[i][j] = ni();
    }

    int K = ni();
    vector<pii> points(K);
    REP(i,K) {
        int r = ni();
        int c = ni();
        occ[r][c] = i+1;
        points[i] = {r,c};
    }


    vi vis(K+1);
    for (int i = 1; i <= K; i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        queue<pii> q;
        q.push(points[i-1]);

        vector<pii> center;

        set<pii> slots;
        int cnt = 0;

        while (!q.empty()) {
            pii point = q.front();
            q.pop();
            cnt += 3;
            center.add(point);

            for (auto dir: dirs) {
                int newR = point.first+dir[0];
                int newC = point.second+dir[1];
                if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
                    int g = occ[newR][newC];
                    if (g > 0 && !vis[g]) {
                        vis[g] = 1;
                        q.push({newR,newC});
                    }
                }
            }
        }


        for (pii point: center) {
            for (auto dir: dirs1) {
                int newR = point.first+dir[0];
                int newC = point.second+dir[1];
                if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
                    int g = occ[newR][newC];
                    if (g == 0) {
                        slots.insert({newR,newC});
                    }
                }
            }
        }

        if (sz(slots) < cnt) {
            cout << "No\n";
            return 0;
        }

        vi gain;
        for (pii slot: slots) {
            gain.add(grid[slot.first][slot.second]);
        }
        sort(gain.begin(),gain.end(),greater<int>());

        for (int j = 0; j < cnt; j++)
            ans += gain[j];
        for (pii point: center) {
            ans += grid[point.first][point.second];
        }
    }
    cout << ans << '\n';
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
covering.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     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