Submission #441642

#	Time	Username	Problem	Language	Result	Execution time	Memory
441642		SlavicG	T-Covering (eJOI19_covering)	C++17	100 / 100	388 ms	23544 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() {
    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;
 
 
    const int N = ni();
    const int M = ni();
    int grid[N][M];
    int occ[N][M];
 
    REP(i,N) REP(j,M) {
        grid[i][j] = ni();
        occ[i][j] = 0;
    }
 
    const 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};
    }
 
    int vis[K+1];
    for(int i = 0;i <= K;i++)
        vis[i] = 0;
    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';
}

• 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