#include <bits/stdc++.h>
#define ll long long
const ll inf = 1e19 + 7;
using namespace std;
ll r, c;
vector<vector<pair<ll, vector<bool>>>> dp;
vector<string> grid;
ll idx = 0, szcnt = 0;
vector<ll> sizes;
vector<pair<ll, ll>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> vis;
vector<vector<ll>> color;
bool lol(ll i, ll j) {
return (i >= 1 && j >= 1 && i <= r && j <= c && !vis[i][j] &&
grid[i][j - 1] != '.');
}
void dfs(ll i, ll j) {
color[i][j] = idx;
vis[i][j] = 1;
if (grid[i][j - 1] != '.')
szcnt += (grid[i][j - 1] - '0');
for (auto [x, y] : dir) {
if (lol(i + x, j + y))
dfs(i + x, j + y);
}
}
void build_dp() {
for (ll i = 1; i <= c; ++i) {
for (ll j = 1; j <= c; ++j) {
for (ll x = 1; x <= i; ++x) {
const auto &prev = dp[x][j - 1];
ll val = prev.first;
const auto &vec = prev.second;
ll add = 0;
vector<bool> visit = vec;
for (ll row = 1; row <= r; ++row) {
if (grid[row][i - 1] == '.')
continue;
ll comp = color[row][i];
if (!visit[comp] && grid[row][i - 1] != '.') {
visit[comp] = 1;
add += sizes[comp];
}
}
if (val + add > dp[i][j].first)
dp[i][j] = {val + add, std::move(visit)};
}
}
}
}
int main() {
cin >> r >> c;
grid.resize(r + 1);
vis.resize(r + 1, vector<bool>(c + 1));
color.resize(r + 1, vector<ll>(c + 1));
sizes.resize(r * c + 2);
for (ll i = 1; i <= r; ++i) {
cin >> grid[i];
}
for (ll i = 1; i <= r; ++i) {
for (ll j = 1; j <= c; ++j) {
if (!vis[i][j] && grid[i][j - 1] != '.') {
dfs(i, j);
sizes[idx] = szcnt;
szcnt = 0;
idx++;
}
}
}
dp.assign(c + 1,
vector<pair<ll, vector<bool>>>(c + 1, {0, vector<bool>(idx + 1)}));
build_dp();
vector<ll> ans(c + 1);
for (ll j = 1, pref = 0; j <= c; ++j) {
ll best = 0;
for (ll i = 1; i <= c; ++i)
best = max(best, dp[i][j].first);
pref = max(pref, best);
cout << pref << "\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
nafta.cpp:3:21: warning: overflow in conversion from 'double' to 'long long int' changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
3 | const ll inf = 1e19 + 7;
| ~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |