oj.uz

Submission #935208

# Submission time Handle Problem Language Result Execution time Memory
935208 2024-02-28T20:04:27 Z amirhoseinfar1385 Nafta (COI15_nafta) C++17
11 / 100
 2 ms 860 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100+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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Runtime error 2 ms 860 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Runtime error 2 ms 860 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -