#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define ll long long
const int N = 2005;
char a[N][N];
int n, m;
bool bio[N][N];
queue <pair <int,int> > q;
int b[N][N], c[N][N], d[N];
int dp[N][N];
void func(int l, int r, int ol, int orr, int kk) {
if (r < l) return;
int mid = (l+r)/2;
int pos = ol;
for (int i=max(mid+1, ol);i<=orr;i++) {
if (dp[mid][kk] < dp[i][kk-1] + c[mid][i]) {
dp[mid][kk] = dp[i][kk-1] + c[mid][i];
pos = i;
}
}
func(l, mid-1, ol, pos, kk);
func(mid+1, r, pos, orr, kk);
}
int main() {
cin >> n >> m;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
cin >> a[i][j];
}
}
for (int j=0;j<m;j++) {
for (int i=0;i<n;i++) {
if (a[i][j] == '.') continue;
if (bio[i][j]) continue;
q.push(mp(i,j));
int suma = 0;
int x, y, my = 0;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
my = max(my, y);
suma += a[x][y] - '0';
bio[x][y] = 1;
q.pop();
for (int kk=-1;kk<2;kk++) {
for (int l=-1;l<2;l++) {
if (kk != 0 && l != 0) continue;
x += kk; y += l;
if (x > n-1 || x < 0 || y > m-1 || y < 0);
else if (bio[x][y]);
else if (a[x][y] == '.');
else q.push(make_pair(x, y));
x -= kk; y -= l;
}
}
}
b[j][j]+=suma;
b[j][my+1]-=suma;
}
}
for (int i=0;i<m;i++) {
for (int j=1;j<m;j++) {
b[i][j] += b[i][j-1];
}
}
for (int i=0;i<m;i++) {
for (int j=m-2;j>=0;j--) {
c[j][i] = c[j+1][i] + b[j+1][i];
}
}
memset(dp, -1, sizeof 1);
for (int i=0;i<m;i++) dp[i][1] = 0;
for (int i=2;i<=m;i++) {
func(0, m-1, 0, m-1, i);
}
for (int i=0;i<m;i++) {
for (int j=0;j<=i;j++) d[i] += b[j][i];
}
for (int i=1;i<=m;i++) {
int res = 0;
for (int j=0;j<m;j++) {
if (dp[j][i] == -1) dp[j][i] = 0;
dp[j][i] += d[j];
res = max(res, dp[j][i]);
}
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
