oj.uz

Submission #935209

# Submission time Handle Problem Language Result Execution time Memory
935209 2024-02-28T20:05:34 Z amirhoseinfar1385 Nafta (COI15_nafta) C++17
100 / 100
 261 ms 119892 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct
8 Correct 7 ms 14428 KB Output is correct
9 Correct 8 ms 15452 KB Output is correct
10 Correct 5 ms 13660 KB Output is correct
11 Correct 5 ms 13676 KB Output is correct
12 Correct 5 ms 13656 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct
8 Correct 7 ms 14428 KB Output is correct
9 Correct 8 ms 15452 KB Output is correct
10 Correct 5 ms 13660 KB Output is correct
11 Correct 5 ms 13676 KB Output is correct
12 Correct 5 ms 13656 KB Output is correct
13 Correct 182 ms 74504 KB Output is correct
14 Correct 204 ms 71364 KB Output is correct
15 Correct 261 ms 119892 KB Output is correct
16 Correct 145 ms 67152 KB Output is correct
17 Correct 152 ms 64116 KB Output is correct
18 Correct 137 ms 64172 KB Output is correct