#include<bits/stdc++.h>
typedef long long ll;
#define fr first
#define sc second
#define pb push_back
#define int ll
#define endl '\n'
using namespace std;
struct Fen{
int n;
vector<int>tree;
Fen(int N){
n=N;
tree.resize(n+1,0);
}
void update(int tar,int x){
while(tar<=n){
tree[tar]+=x;
tar+=(tar&-tar);
}
}
int query(int tar){
int res=0;
while(tar){
res+=tree[tar];
tar-=(tar&-tar);
}
return res;
}
};
int n,m,k;
char grid[2002][2002];
int w[2002][2002];
vector<pair<pair<int,int>,int>>ara;
int dp[2002][2002];
void f(int left,int right,int l,int r,int t){
if(left>right)return;
int mid=((left+right+1)>>1);
pair<int,int>res={-1,-1};
for(int i=l;i<=min(mid,r);i++){
int cos=dp[t-1][i]+w[i][mid];
res=max(res,{cos,i});
}
dp[t][mid]=res.fr;
f(left,mid-1,l,res.sc,t);
f(mid+1,right,res.sc,r,t);
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>grid[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(grid[i][j]=='.')continue;
int l=m+1,r=0,sum=0;
queue<pair<int,int>>q;q.push({i,j});
while(q.size()){
pair<int,int>pos=q.front();
q.pop();
l=min(l,pos.sc);
r=max(r,pos.sc);
sum+=grid[pos.fr][pos.sc]-'0';
grid[pos.fr][pos.sc]='.';
if(pos.fr!=1&&grid[pos.fr-1][pos.sc]!='.'){
q.push({pos.fr-1,pos.sc});
}
if(pos.sc!=1&&grid[pos.fr][pos.sc-1]!='.'){
q.push({pos.fr,pos.sc-1});
}
if(pos.fr!=n&&grid[pos.fr+1][pos.sc]!='.'){
q.push({pos.fr+1,pos.sc});
}
if(pos.sc!=m&&grid[pos.fr][pos.sc+1]!='.'){
q.push({pos.fr,pos.sc+1});
}
}
ara.pb({{l,r},sum});
}
}
k=ara.size();
Fen fen(m);
{
vector<pair<int,int>>up[m+1];
for(pair<pair<int,int>,int>p:ara){
up[p.fr.fr].pb({p.fr.sc,p.sc});
}
for(int i=1;i<=m;i++){
for(pair<int,int>x:up[i]){
fen.update(x.fr,x.sc);
}
up[i].clear();
int fir=fen.query(m);
int toplam=fir-fen.query(i-1);
w[i][m+1]=toplam;
for(int j=1;j<=m;j++){
w[i][j]+=toplam;
}
for(int j=i+1;j<=m;j++){
w[j][i]-=fir-fen.query(j-1);
}
}
for(pair<pair<int,int>,int>p:ara){
up[p.fr.sc].pb({p.fr.fr,p.sc});
}
fen.tree.resize(0);fen.tree.resize(m+1,0);
for(int i=m;i>=1;i--){
for(pair<int,int>x:up[i]){
fen.update(x.fr,x.sc);
}
up[i].clear();
for(int j=i;j>=1;j--){
w[j][i]-=fen.query(j);
}
}
}
for(int i=1;i<=m+1;i++){
for(int j=1;j<=i;j++){
dp[1][i]=max(dp[1][i],w[j][i]);
}
}
cout<<dp[1][m+1]<<endl;
for(int i=2;i<=m;i++){
f(1,m+1,1,m+1,i);
cout<<dp[i][m+1]<<endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
