This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;
const int MAX_N = 2e3 + 10;
const int INF = 1e9 + 7;
const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
char table[MAX_N][MAX_N];
int value[MAX_N], intersect[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
void solve(const int &k, const int &l, const int &r, const int &a, const int &b) {
if(l > r) {
return;
}
int mid = (l + r) / 2, pos;
dp[k][mid] = -INF;
for(int i = a; i <= min(mid, b); i++) {
int res = dp[k - 1][i - 1] + value[mid] - intersect[i - 1][mid];
if(dp[k][mid] < res) {
dp[k][mid] = res;
pos = i;
}
}
solve(k, l, mid - 1, a, pos);
solve(k, mid + 1, r, pos, b);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int R, S;
cin >> R >> S;
for(int i = 1; i <= R; i++) {
cin >> (table[i] + 1);
}
queue <pair <int, int>> q;
for(int i = 1; i <= R; i++) {
for(int j = 1; j <= S; j++) {
if(visited[i][j] == true or table[i][j] == '.') {
continue;
}
visited[i][j] = true;
q.emplace(i, j);
int min_S = S, max_S = 0, sz = 0;
while(!q.empty()) {
auto [ux, uy] = q.front();
q.pop();
sz += table[ux][uy] - '0';
min_S = min(min_S, uy);
max_S = max(max_S, uy);
for(int i = 0; i < 4; i++) {
int vx = ux + d[i][0], vy = uy + d[i][1];
if(vx < 1 or vx > R or vy < 1 or vy > S or visited[vx][vy] == true or table[vx][vy] == '.') {
continue;
}
visited[vx][vy] = true;
q.emplace(vx, vy);
}
}
for(int s = min_S; s <= max_S; s++) {
value[s] += sz;
for(int s2 = s + 1; s2 <= max_S; s2++) {
intersect[s][s2] += sz;
}
}
}
}
for(int i = 1; i <= S; i++) {
dp[1][i] = value[i];
}
cout << *max_element(dp[1] + 1, dp[1] + S + 1) << '\n';
for(int i = 2; i <= S; i++) {
solve(i, i, S, i, S);
cout << *max_element(dp[i] + 1, dp[i] + S + 1) << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |