제출 #935209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935209		amirhoseinfar1385	Nafta (COI15_nafta)	C++17	100 / 100	261 ms	119892 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10;
struct fenwick{
	int fn[maxn];
	void add(int i,int w){
		i++;
		while(i<maxn){
			fn[i]+=w;
			i+=(i&(-i));
		}
	}
	int pors(int i){
		i++;
		int ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;	
	}
}fn;
int c[maxn][maxn],dp[maxn][maxn],all[maxn][maxn],n,m,fl=maxn+1,fr=-1,sum=0,vis[maxn][maxn],add[maxn];
vector<pair<int,int>>del[maxn];
void vorod(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='.'){
				all[i][j]=-1;
			}
			else{
				all[i][j]=c-'0';
			}
		}
	}
}

void dfs(int r,int c){
	if(r<1||r>n||c<1||c>m||vis[r][c]==1||all[r][c]==-1){
		return ;
	}
	vis[r][c]=1;
	sum+=all[r][c];
	fr=max(fr,c);
	fl=min(fl,c);
	dfs(r,c-1);
	dfs(r,c+1);
	dfs(r-1,c);
	dfs(r+1,c);
}

void pre(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(all[i][j]==-1||vis[i][j]==1){
				continue;
			}
			fr=-1;
			sum=0;
			fl=maxn+1;
			dfs(i,j);
			add[fl]+=sum;
			del[fr+1].push_back(make_pair(fl,sum));
		}
	}
	for(int i=1;i<=m;i++){
		fn.add(0,add[i]);
		fn.add(i,-add[i]);
		for(auto x:del[i]){
			fn.add(x.first,x.second);
			fn.add(0,-x.second);
		}
		for(int j=i-1;j>=0;j--){
			c[i][j]=fn.pors(j);
		//	cout<<i<<" "<<j<<" "<<c[i][j]<<endl;
		}
	}
}

void call(int ind,int l,int r,int tl,int tr){
	if(l>r){
		return ;
	}
	if(tl==tr){
		for(int i=l;i<=r;i++){
			dp[ind][i]=dp[ind-1][tl]+c[i][tl];
		}
		return ;
	}
	int mid=(l+r)>>1;
	int mx=-1,wh=0;
	for(int i=tl;i<=min(mid-1,tr);i++){
		if(dp[ind-1][i]+c[mid][i]>mx){
			wh=i;
			mx=dp[ind-1][i]+c[mid][i];
		}
	}
	dp[ind][mid]=mx;
	call(ind,l,mid-1,tl,wh);
	call(ind,mid+1,r,wh,tr);
}

void solve(){
	for(int i=1;i<=m;i++){
		if(i==1){
			for(int j=1;j<=m;j++){
				dp[i][j]=c[j][0];
			}
			continue;
		}
		call(i,1,m,1,m);
	}
}

void khor(){
	for(int i=1;i<=m;i++){
		int res=-1;
		for(int j=1;j<=m;j++){
			res=max(res,dp[i][j]);
		}
		cout<<res<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
	solve();
	khor();
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66