#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
const int N = 2e3 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int d[5] = {0, 1, 0, -1, 0};
const int M = 4e6 + 4;
int r, c, cnt, vis[N][N], sum[M], fl[M], fr[M], dc[N], col[N], f[M], cost[N][N], ic[N];
int dp[N][N], now;
string a[N];
bool maxi (int &x, int y){
if (y > x)
return x = y, 1;
return 0;
}
bool ok (int i, int j){
return i > 0 && j > 0 && i <= r && j <= c && a[i][j] != '.';
}
void dfs (int i, int j){
vis[i][j] = cnt;
fr[cnt] = max (fr[cnt], j);
fl[cnt] = min (fl[cnt], j);
sum[cnt] += a[i][j] - '0';
forf (k, 0, 5){
int ni = i + d[k], nj = j + d[k + 1];
if (ok(ni, nj) && !vis[ni][nj])
dfs(ni, nj);
}
}
void calc (int l, int r, int opl, int opr){
if (l > r) return;
// if (now == 2){
// cout << l << " " << r << " " << opl << " " << opr << "\n";
// }
int mid = (l + r) >> 1;
int op = -1;
forr (i, opl, min(mid, opr)){
if (maxi(dp[mid][now], dp[i - 1][now - 1] + cost[i][mid]))
op = i;
}
//cout << dp[mid][now] << " " << op << '\n';
calc(l, mid - 1, opl, op);
calc (mid + 1, r, op, opr);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> r >> c;
forr (i, 1, r){
cin >> a[i];
a[i] = '.' + a[i];
}
forr (i, 1, c)
fl[i] = c + 1;
memset (dp, -63, sizeof dp);
forr (i, 0, c)
dp[i][0] = 0, dp[0][i] = 0;
forr (i, 1, r)
forr (j, 1, c)
if (!vis[i][j] && a[i][j] != '.'){
++cnt;
dfs(i, j);
// dc[fl[cnt]] += sum[cnt];
// ic[fr[cnt]] += sum[cnt];
// cout << sum[cnt] << " " << fl[cnt] << " " << fr[cnt] << "\n";
}
forr (j, 1, c){
col[j] = 0;
forr (i, 1, r)
f[vis[i][j]] = 1;
forr (i, 1, r){
ic[fl[vis[i][j]]] += sum[vis[i][j]] * f[vis[i][j]];
f[vis[i][j]] = 0;
}
ford (i, j, 1)
cost[i][j] = cost[i + 1][j] + ic[i], ic[i] = 0;
// forr (i, 1, j)
// cout << cost[i][j] << " ";
// cout << "\n";
}
forr (i, 1, c)
dp[i][1] = cost[1][i];
forr (i, 2, c){
now = i;
calc(1, c, 1, c);
}
forr (i, 1, c){
int ans = 0;
forr (j, 1, c)
maxi(ans, dp[j][i]);
cout << ans << "\n";
}
return 0;
}
/*
*/
Compilation message
nafta.cpp: In function 'void dfs(int, int)':
nafta.cpp:49:38: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
49 | int ni = i + d[k], nj = j + d[k + 1];
| ~~~~~~~^
nafta.cpp:11:46: note: within this loop
11 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
| ^
nafta.cpp:48:2: note: in expansion of macro 'forf'
48 | forf (k, 0, 5){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
