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 endl '\n'
using namespace std;
const int maxn = 2010;
int n, m, used[maxn][maxn];
char c[maxn][maxn];
vector<long long> dp_bef(maxn), dp_aft(maxn);
struct cell{
int x, y;
cell operator+(cell c){
return {x + c.x, y + c.y};
}
bool inRange(){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
};
cell dir[4] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
void read(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> c[i][j];
}
}
}
void bfs(cell beg, int col){
queue<cell> q;
q.push(beg);
used[beg.x][beg.y] = col;
while(!q.empty()){
cell e = q.front();
q.pop();
for(int i = 0;i < 4;i++){
cell curr = e + dir[i];
if(!curr.inRange() || used[curr.x][curr.y])
continue;
if(c[curr.x][curr.y] == '.')
continue;
used[curr.x][curr.y] = col;
q.push(curr);
}
}
}
void preCompute(){
int cnt = 1;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(c[i][j] != '.' && !used[i][j]){
bfs({i, j}, cnt);
cnt++;
}
}
}
}
int cycle = 1, s;
long long calc(int i, int mid){
long long sum = 0;
queue<cell> q;
cycle++;
for(int j = 1;j <= n;j++){
if(mid <= m && c[j][mid] != '.'){
q.push({j, mid});
used[j][mid] = cycle;
sum += c[j][mid] - '0';
}
}
s = sum;
while(!q.empty()){
cell t = q.front();
q.pop();
for(int j = 0;j < 4;j++){
cell curr = dir[j] + t;
if(!curr.inRange() || used[curr.x][curr.y] == cycle)
continue;
if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i)
continue;
sum += c[curr.x][curr.y] - '0';
q.push(curr);
used[curr.x][curr.y] = cycle;
}
}
if(i == 0)
return sum;
q = queue<cell>();
for(int j = 1;j <= n;j++){
if(c[j][i] != '.' && used[j][i] != cycle){
q.push({j, i});
used[j][i] = cycle;
}
}
while(!q.empty()){
cell t = q.front();
q.pop();
for(int j = 0;j < 4;j++){
cell curr = dir[j] + t;
if(!curr.inRange() || used[curr.x][curr.y] == cycle)
continue;
if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i)
continue;
sum += c[curr.x][curr.y] - '0';
q.push(curr);
used[curr.x][curr.y] = cycle;
}
}
return sum;
}
void divide(int l, int r, int optl, int optr){
if(l > r)
return;
int mid = (l + r) / 2;
long long best = LLONG_MIN, k;
for(int i = optl;i <= min(mid, optr);i++){
long long curr = dp_bef[i - 1] + calc(i - 1, mid);
if(curr > best){
best = curr;
k = i;
}
}
dp_aft[mid] = best;
divide(l, mid - 1, optl, k);
divide(mid + 1, r, k, optr);
}
void solve(){
long long ans = 0;
for(int i = 1;i <= m;i++){
dp_bef[i] = calc(0, i);
ans = max(ans, dp_bef[i] + calc(i, m + 1) - s);
}
cout << ans << endl;
for(int i = 2;i <= m;i++){
divide(1, m, 1, m);
dp_bef = dp_aft;
long long ans = 0;
for(int i = 1;i <= m;i++){
ans = max(ans, dp_aft[i] + calc(i, m + 1) - s);
}
cout << ans << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
read();
solve();
return 0;
}
Compilation message (stderr)
nafta.cpp: In function 'void divide(int, int, int, int)':
nafta.cpp:132:11: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
132 | divide(l, mid - 1, optl, k);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |