이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL<<x)
#define epr(...) fprintf(stderr, __VA_ARGS__); fflush(stderr)
#define db(x) cerr << #x << " = " << x << '\n'
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << " = "; for (auto xxxx: a) cerr << xxxx << " "; cerr << '\n'
typedef long long ll;
typedef double dbl;
const int INF = 1e9 + 17;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int solve(int n, int m, vector<vector<int>> a, int k, vector<pair<int, int>> t) {
auto check = [&](int i, int j) {
return i >= 0 && i < n && j >= 0 && j < m;
};
vector<vector<int>> id(n, vector<int>(m, -1));
for (int i = 0; i < k; ++i) {
id[t[i].F][t[i].S] = i;
}
vector<vector<int>> e(k);
for (int i = 0; i < k; ++i) {
for (int x = -2; x <= 2; ++x) {
for (int y = -2; y <= 2; ++y) {
pair<int,int> to = {t[i].F + x, t[i].S + y};
if (check(to.F, to.S) && abs(x) + abs(y) != 0 && abs(x) + abs(y) <= 2 && id[to.F][to.S] != -1) {
e[i].pb(id[to.F][to.S]);
}
}
}
}
vector<bool> used(k, false);
vector<int> comp;
function<void(int)> dfs = [&](int v) {
used[v] = true;
comp.pb(v);
for (auto u: e[v]) {
if (!used[u]) {
dfs(u);
}
}
};
int res = 0;
for (int i = 0; i < k; ++i) {
res += a[t[i].F][t[i].S];
}
vector<vector<bool>> taken(n, vector<bool>(m, false));
for (int i = 0; i < k; ++i) {
if (!used[i]) {
comp = {};
dfs(i);
vector<pair<int,int>> cur;
for (auto v: comp) {
for (int d = 0; d < 4; ++d) {
pair<int,int> to = {t[v].F + dx[d], t[v].S + dy[d]};
if (check(to.F, to.S) && id[to.F][to.S] == -1 && !taken[to.F][to.S]) {
taken[to.F][to.S] = true;
cur.pb(to);
}
}
}
int need = sz(comp) * 3;
if (sz(cur) < need) {
return -INF;
}
for (auto it: cur) {
res += a[it.F][it.S];
}
if (sz(cur) > need) {
int mn = INF;
for (auto it: cur) {
if (a[it.F][it.S] < mn) {
mn = a[it.F][it.S];
}
}
res -= mn;
}
}
}
return res;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
}
}
int k;
scanf("%d", &k);
vector<pair<int,int>> t(k);
for (int i = 0; i < k; ++i) {
scanf("%d %d", &t[i].F, &t[i].S);
}
int answer = solve(n, m, a, k, t);
if (answer == -INF) {
printf("No\n");
} else {
printf("%d\n", answer);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
covering.cpp: In function 'int main()':
covering.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
covering.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
102 | scanf("%d", &a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
covering.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
110 | scanf("%d %d", &t[i].F, &t[i].S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |