#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<bool>> vvb;
const int INF = numeric_limits<int>::max()/2;
int R;
vector<int> oil {0};
vector<vector<int>> pool;
vector<vector<int>> pools;
void calc (vector<int> &dp, vvb &dp_t, vector<int> &new_dp, vvb &new_dp_t, int l, int r, int optl, int optr) {
if (l >= r) return;
int mid = (l + r) / 2;
int opt = -1;
for (int i = optl; i < optr; i++) {
if (i >= mid) break;
int x = dp[i];
vector<bool> t = dp_t[i];
for (auto &it: pools[mid-1]) {
if (!t[it]) {
x += oil[it];
t[it] = true;
}
}
if (new_dp[mid] < x) {
new_dp[mid] = x;
new_dp_t[mid] = t;
opt = i;
}
}
calc(dp, dp_t, new_dp, new_dp_t, l, mid, optl, opt+1);
calc(dp, dp_t, new_dp, new_dp_t, mid+1, r, opt, optr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int r, s;
cin >> r >> s;
R = r;
vector<vector<int>> m (r+2, vector<int>(s+2, -1));
for (int i = 0; i < r; i++) {
for (int j = 0; j < s; j++) {
char c;
cin >> c;
if (c != '.') {
m[i+1][j+1] = c - '0';
}
}
}
int cnt = 1;
pool = vector<vector<int>>(r+2, vector<int>(s+2, 0));
for (int i = 0; i < r; i++) {
for (int j = 0; j < s; j++) {
if (m[i+1][j+1] != -1 && pool[i+1][j+1] == 0) {
int cur = cnt++;
pool[i+1][j+1] = cur;
oil.push_back(0);
queue<pair<int, int>> q {};
q.push({i+1, j+1});
while (!q.empty()) {
auto[x, y] = q.front();
q.pop();
oil[cur] += m[x][y];
vector<pair<int, int>> nb {{x, y-1}, {x, y+1}, {x-1, y}, {x+1, y}};
for (auto[itx, ity] : nb) {
if (m[itx][ity] != -1 && pool[itx][ity] == 0) {
pool[itx][ity] = cur;
q.push({itx, ity});
}
}
}
}
}
}
pools = vector<vector<int>> (s);
for (int i = 0; i < s; i++) {
vector<bool> t (r, false);
for (int j = 0; j < R; j++) {
if (!t[pool[j+1][i+1]]) {
t[pool[j+1][i+1]] = true;
pools[i].push_back(pool[j+1][i+1]);
}
}
}
vector<int> dp (s+1, 0);
vector<vector<bool>> dp_t (s+1, vector<bool>(cnt, false));
//vector<int> new_dp = dp;
//vector<vector<bool>> new_dp_t = dp_t;
for (int i = 0; i < s; i++) {
vector<int> new_dp (s+1, -1);
vector<vector<bool>> new_dp_t (s+1, vector<bool>(cnt, false));
calc(dp, dp_t, new_dp, new_dp_t, 1, s+1, 0, s+1);
cout << *max_element(new_dp.begin(), new_dp.end()) << "\n";
dp = new_dp;
dp_t = new_dp_t;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
