#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 2e3 + 5;
int n, m, dp[N][N], cal[N][N]; // dp[i][j] = max number of oil after picking i columns including column j
char a[N][N];
bool visited[N][N];
map <int, vector <pii>> mp;
struct fenwick {
int fw[N];
void update(int idx, int val){
if (idx >= N) return;
fw[idx] += val;
update(idx + (idx & -idx), val);
}
int query(int idx){
if (idx <= 0) return 0;
return fw[idx] + query(idx - (idx & -idx));
}
} f;
void bfs(int r, int c){
queue <pii> q; q.emplace(r, c);
int sum = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
visited[r][c] = true;
int mn = inf, mx = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
sum += a[x][y] - '0';
mn = min(mn, y);
mx = max(mx, y);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '.' || visited[nx][ny]) continue;
visited[nx][ny] = true;
q.emplace(nx, ny);
}
}
mp[mx].emb(mn, sum);
// cout << mn << " -> " << mx << ": " << sum << "\n";
}
signed main(){
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '.' || visited[i][j]) continue;
bfs(i, j);
}
}
for (int r = m; r >= 1; r--) {
for (auto [l, sum] : mp[r]) f.update(l, sum);
for (int l = r; l >= 1; l--) cal[l][r] = f.query(l);
}
// cout << "----------------------------\n";
// for (int i = 1; i <= m; i++) {
// for (int j = i + 1; j <= m; j++) {
// cout << i << " -> " << j << ": " << cal[i][j] << "\n";
// }
// }
for (int i = 1; i <= m; i++) dp[1][i] = cal[i][i];
for (int k = 2; k <= m; k++) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j < i; j++) {
dp[k][i] = max(dp[k][i], dp[k - 1][j] + cal[i][i] - cal[j][i]);
}
// cout << dp[k][i] << "\n";
}
}
for (int i = 1; i <= m; i++) cout << *max_element(dp[i] + 1, dp[i] + 1 + m) << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |