이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pb push_back
#define endl '\n'
using namespace std;
const int MOD = 1e9+7;
const int N = 1e3;
int n, m, k, g[N][N], x[N * 1000], y[N * 1000], ans = -1;
void dfs(int nu, bool used[N][N], int p) {
if (nu == k) {
ans = max(ans, p);
return;
}
if (used[x[nu]][y[nu]]) {
return;
}
if (x[nu] < n - 1 and y[nu] < m - 1 and y[nu] and !used[x[nu]][y[nu]] and !used[x[nu]][y[nu] - 1] and !used[x[nu]][y[nu] + 1] and !used[x[nu] + 1][y[nu]]) { // down
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu]][y[nu] + 1] = used[x[nu] + 1][y[nu]] = 1;
p += g[x[nu]][y[nu]];
p += g[x[nu]][y[nu] - 1];
p += g[x[nu]][y[nu] + 1];
p += g[x[nu] + 1][y[nu]];
dfs(nu + 1, used, p);
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu]][y[nu] + 1] = used[x[nu] + 1][y[nu]] = 0;
p -= g[x[nu]][y[nu]];
p -= g[x[nu]][y[nu] - 1];
p -= g[x[nu]][y[nu] + 1];
p -= g[x[nu] + 1][y[nu]];
}
if (x[nu] and y[nu] < m - 1 and y[nu] and !used[x[nu]][y[nu]] and !used[x[nu]][y[nu] - 1] and !used[x[nu]][y[nu] + 1] and !used[x[nu] - 1][y[nu]]) { // up
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu]][y[nu] + 1] = used[x[nu] - 1][y[nu]] = 1;
p += g[x[nu]][y[nu]];
p += g[x[nu]][y[nu] - 1];
p += g[x[nu]][y[nu] + 1];
p += g[x[nu] - 1][y[nu]];
dfs(nu + 1, used, p);
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu]][y[nu] + 1] = used[x[nu] - 1][y[nu]] = 0;
p -= g[x[nu]][y[nu]];
p -= g[x[nu]][y[nu] - 1];
p -= g[x[nu]][y[nu] + 1];
p -= g[x[nu] - 1][y[nu]];
}
if (x[nu] < n - 1 and x[nu] and y[nu] and !used[x[nu]][y[nu]] and !used[x[nu]][y[nu] - 1] and !used[x[nu] + 1][y[nu]] and !used[x[nu] - 1][y[nu]]) { // left
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu] + 1][y[nu]] = used[x[nu] - 1][y[nu]] = 1;
p += g[x[nu]][y[nu]];
p += g[x[nu]][y[nu] - 1];
p += g[x[nu] + 1][y[nu]];
p += g[x[nu] - 1][y[nu]];
dfs(nu + 1, used, p);
used[x[nu]][y[nu]] = used[x[nu]][y[nu] - 1] = used[x[nu] + 1][y[nu]] = used[x[nu] - 1][y[nu]] = 0;
p -= g[x[nu]][y[nu]];
p -= g[x[nu]][y[nu] - 1];
p -= g[x[nu] + 1][y[nu]];
p -= g[x[nu] - 1][y[nu]];
}
if (x[nu] < n - 1 and x[nu] and y[nu] < m - 1 and !used[x[nu]][y[nu]] and !used[x[nu]][y[nu] + 1] and !used[x[nu] + 1][y[nu]] and !used[x[nu] - 1][y[nu]]) { // right
used[x[nu]][y[nu]] = used[x[nu]][y[nu] + 1] = used[x[nu] + 1][y[nu]] = used[x[nu] - 1][y[nu]] = 1;
p += g[x[nu]][y[nu]];
p += g[x[nu]][y[nu] + 1];
p += g[x[nu] + 1][y[nu]];
p += g[x[nu] - 1][y[nu]];
dfs(nu + 1, used, p);
used[x[nu]][y[nu]] = used[x[nu]][y[nu] + 1] = used[x[nu] + 1][y[nu]] = used[x[nu] - 1][y[nu]] = 0;
p -= g[x[nu]][y[nu]];
p -= g[x[nu]][y[nu] + 1];
p -= g[x[nu] + 1][y[nu]];
p -= g[x[nu] - 1][y[nu]];
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> g[i][j];
}
}
cin >> k;
for (int i = 0; i < k; ++i) {
cin >> x[i] >> y[i];
}
bool used[N][N];
memset(used, 0, sizeof used);
dfs(0,used,0);
if (ans == -1)
cout << "No\n";
else
cout << ans << endl;
}
# | 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... |