#include<bits/stdc++.h>
using namespace std;
#define int long long
const vector<vector<pair<int, int>>> T = {{{0, 0}, {0, -1}, {0, 1}, {1, 0}}, {{0, 0}, {0, -1}, {0, 1}, {-1, 0}}, {{0, 0}, {-1, 0}, {1, 0}, {0, 1}}, {{0, 0}, {-1, 0}, {1, 0}, {0, -1}}};
const int INF = 2e18;
int n, m;
vector<vector<int>> a;
inline bool check(int x, int y){
return x >= 0 && x < n && y >= 0 && y < m;
}
inline void upd(int &x, int y) {
if(y > x)
x = y;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
a.assign(n, vector<int>(m));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> a[i][j];
}
}
int k;
cin >> k;
vector<pair<int, int>> t(k);
for(int i = 0; i < k; ++i)
cin >> t[i].first >> t[i].second;
sort(t.begin(), t.end());
vector<vector<int>> dp(t.size(), vector<int>(4, -INF));
for(int i = 0; i < 4; ++i){
bool ok = 1;
int sum = 0;
for(auto pp : T[i]){
ok &= check(t[0].first + pp.first, t[0].second + pp.second);
if(ok){
sum += a[t[0].first + pp.first][t[0].second + pp.second];
} else{
break;
}
}
if(ok){
dp[0][i] = sum;
}
}
for(int i = 1; i < k; ++i) {
for(int j = 0; j < 4; ++j){
bool ok = 1;
int sum = 0;
vector<pair<int, int>> v1;
for(auto pp : T[i]){
ok &= check(t[i].first + pp.first, t[i].second + pp.second);
v1.emplace_back(t[i].first + pp.first, t[i].second + pp.second);
if(ok){
sum += a[t[i].first + pp.first][t[i].second + pp.second];
} else{
break;
}
}
if(ok){
sort(v1.begin(), v1.end());
for(int jj = 0; jj < 4; ++jj){
if(dp[i - 1][jj] == -INF)
continue;
vector<pair<int, int>> v2;
for(auto pp : T[jj]){
v2.emplace_back(t[i - 1].first + pp.first, t[i - 1].second + pp.second);
}
sort(v2.begin(), v2.end());
bool good = 1;
for(auto pp : v1){
auto it = lower_bound(v2.begin(), v2.end(), pp);
good &= it == v2.end() || *it != pp;
if(!good){
break;
}
}
if(good){
upd(dp[i][j], dp[i - 1][jj] + sum);
}
}
}
}
}
int ans = -INF;
for(int i = 0; i < 4; i++){
upd(ans, dp[k - 1][i]);
}
if(ans == -INF){
cout << "No";
} else{
cout << ans;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |