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 MAX 2005
char ch[MAX][MAX];
typedef std::pair<int,int> pii;
bool visitou[MAX][MAX];
int inter[MAX][MAX];
int soma[MAX];
int prev[MAX];
int tab[MAX];
void DP(int l,int r,int la,int ra){
if(l > r) return;
int mid = (l + r) / 2, lst = 0;
for(int i = la; i <= std::min(mid - 1, r); i++){
int cost = prev[i] + soma[mid] - inter[i][mid];
if(cost > tab[mid]){
tab[mid] = cost;
lst = i;
}
}
DP(l, mid - 1, la, lst);
DP(mid + 1, r, lst, ra);
return;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N,M;
std::cin>>N>>M;
for(int i=0;i!=N;++i){
for(int j=0;j!=M;++j){
std::cin>>ch[i][j];
}
}
for(int i=0;i!=N;++i){
for(int j=0;j!=M;++j){
if(ch[i][j]=='.'||visitou[i][j])continue;
std::queue<pii> queue;
queue.push({i,j});
long long total=0;
int left=j,right=j;
while(queue.size()){
auto __ = queue.front();
queue.pop();
if(__.first<0||__.second<0)continue;
if(__.first>=N||__.second>=M)continue;
if(ch[__.first][__.second]=='.')continue;
if(visitou[__.first][__.second])continue;
visitou[__.first][__.second]=1;
total+=ch[__.first][__.second]-'0';
left=std::min(left,__.second);
right=std::max(right,__.second);
queue.push({__.first+1,__.second});
queue.push({__.first-1,__.second});
queue.push({__.first,__.second+1});
queue.push({__.first,__.second-1});
}
soma[left]+=total;
soma[right+1]-=total;
for(int k=left;k!=right+1;++k){
inter[k][left]+=total;
inter[k][right+1]-=total;
}
}
}
{
int s=0;
for(int i=0;i!=M;++i){
s+=soma[i];
soma[i]=s;
}
for(int i=0;i!=M;++i){
int s=0;
for(int j=0;j!=M;++j){
s+=inter[i][j];
inter[i][j]=s;
}
}
}
int resp1=0;
for(int i=0;i!=M;++i){
prev[i]=soma[i];
resp1=std::max(resp1,soma[i]);
}
std::cout<<resp1<<"\n";
for(int i=1;i!=M;++i){
DP(i,M-1,0,M-1);
std::cout<<*std::max_element(tab,&tab[M])<<"\n";
for(int j=0;j!=M;++j){
prev[j]=tab[j];
tab[j] = INT32_MIN;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |