Submission #1326376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326376		SeDunion	T-Covering (eJOI19_covering)	C++20	100 / 100	207 ms	57512 KiB

covering

#include <iostream>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
 
using namespace std;
using ll = long long;

const int N = 1e6 + 66;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int n, m, a[N], ans, t[N], used[N], ts;

int id(int i, int j) {
    return i * m + j;
}

vector<int>as, g[N];

void dfs(int v) {
    used[v] = 1;
    if (t[v]) ts++;
    else as.emplace_back(a[v]);
    for (int to : g[v]) if (!used[to]) dfs(to);
}

void solve() {
    cin >> n >> m;
    for (int i = 0 ; i < n * m ; ++ i) cin >> a[i];
    int k;
    cin >> k;
    for (int i = 0 ; i < k ; ++ i) {
        int x, y;
        cin >> x >> y;
        t[id(x, y)] = 1;
        ans += a[id(x, y)];
        for (int j = 0 ; j < 4 ; ++ j) {
            int nx = x + dx[j], ny = y + dy[j];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                g[id(x, y)].emplace_back(id(nx, ny));
                g[id(nx, ny)].emplace_back(id(x, y));
            }
        }
    }
    for (int i = 0 ; i < n * m ; ++ i) {
        if (used[i]) continue;
        ts = 0, as.clear();
        dfs(i);
        if (as.size() < 3 * ts) {
            cout << "No";
            return;
        }
        sort(as.rbegin(), as.rend());
        for (int k = 0 ; k < 3 * ts ; ++ k) ans += as[k];
    }
    cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
		cout << "\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