Submission #1051032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051032		PieArmy	Nafta (COI15_nafta)	C++17	100 / 100	183 ms	85936 KiB

nafta

#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});
			sum=grid[i][j]-'0';
			grid[i][j]='.';
			while(q.size()){
				pair<int,int>pos=q.front();
				q.pop();
				l=min(l,pos.sc);
				r=max(r,pos.sc);
				if(pos.fr!=1&&grid[pos.fr-1][pos.sc]!='.'){
					sum+=grid[pos.fr-1][pos.sc]-'0';
					grid[pos.fr-1][pos.sc]='.';
					q.push({pos.fr-1,pos.sc});
				}
				if(pos.sc!=1&&grid[pos.fr][pos.sc-1]!='.'){
					sum+=grid[pos.fr][pos.sc-1]-'0';
					grid[pos.fr][pos.sc-1]='.';
					q.push({pos.fr,pos.sc-1});
				}
				if(pos.fr!=n&&grid[pos.fr+1][pos.sc]!='.'){
					sum+=grid[pos.fr+1][pos.sc]-'0';
					grid[pos.fr+1][pos.sc]='.';
					q.push({pos.fr+1,pos.sc});
				}
				if(pos.sc!=m&&grid[pos.fr][pos.sc+1]!='.'){
					sum+=grid[pos.fr][pos.sc+1]-'0';
					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);
			for(int j=1;j<=m+1;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;
}

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