이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define ull unsigned ll
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(l, r) cerr << "[" << (#l) << ", " << (#r) << "] = ", _print(l, r), cerr << '\n'
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
template<class iter>
void _print(iter _first, iter _last) {
while (_first != _last) {
std::cerr << *(_first) << ' ';
++_first;
}
}
const int N = 1 << 11;
const int S = 2e7 + 64;
const int INF = 1e9 + 9;
const ll MAX = 2e18 + 18;
const int LOG = 30;
const int MOD = 998244353;
const int P = 79;
const int B = 256;
using namespace std;
using namespace __gnu_pbds;
const int dx[4] = {-1, +1, 0, 0};
const int dy[4] = {0, 0, -1, +1};
char a[N][N];
bool used[N][N];
int n, m, lb[N * N], rb[N * N], cost[N * N], prep[N][N], C[N][N], opt[N][N], dp[N][N];
void dfs(int x, int y, int comp) {
used[x][y] = true;
cost[comp] += a[x][y] - '0';
lb[comp] = min(lb[comp], y);
rb[comp] = max(rb[comp], y);
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= n || ny >= m || nx < 0 || ny < 0)
continue;
if (a[nx][ny] != '.' && !used[nx][ny])
dfs(nx, ny, comp);
}
}
void solve(int l, int r, int optl, int optr, int j) {
if (l > r)
return;
int mid = (l + r) >> 1;
point nxt(-INF, -1);
for (int k = optl; k <= min(mid - 1, optr); ++k)
nxt = max(nxt, point(dp[k][j - 1] + C[k][mid], k));
dp[mid][j] = nxt.first;
solve(l, mid - 1, optl, nxt.second, j);
solve(mid + 1, r, nxt.second, optr, j);
}
int32_t main() {
fast_io;
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> a[i][j];
int cnt = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (!used[i][j] && a[i][j] != '.')
lb[cnt] = rb[cnt] = j, dfs(i, j, cnt++);
for (int i = 0; i < cnt; ++i)
prep[lb[i]][rb[i]] += cost[i];
for (int len = 2; len <= m; ++len)
for (int i = 0, j = i + len - 1; j < m; ++i, ++j)
prep[i][j] += prep[i + 1][j] + prep[i][j - 1] - prep[i + 1][j - 1];
for (int i = 0; i < m; ++i) {
C[i][i] = dp[i][1] = prep[0][m - 1] - (i ? prep[0][i - 1] : 0) - prep[i + 1][m - 1];
for (int j = i + 1; j < m; ++j)
C[i][j] = prep[i + 1][m - 1] - prep[j + 1][m - 1] - prep[i + 1][j - 1];
}
for (int j = 2; j <= m; ++j)
solve(0, m - 1, 0, m - 1, j);
for (int j = 1; j <= m; ++j) {
int mx = 0;
for (int i = 0; i < m; ++i)
mx = max(mx, dp[i][j]);
cout << mx << '\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... |