Submission #640446

#	Time	Username	Problem	Language	Result	Execution time	Memory
640446		itnes	Nafta (COI15_nafta)	C++14	100 / 100	505 ms	70016 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN=2e3+7,nTree=(1<<11);
int arr[MAXN][MAXN];
struct seg_tree{
	int T[nTree<<1];
	seg_tree(){
		for(int i=0;i<(nTree<<1);++i) T[i]=0;
	}
	void update(int l,int r,int val){
		if(l>r) return;
		l+=nTree; r+=nTree;
		T[l]+=val;
		if(l<r) T[r]+=val;
		while(l<r-1){
			if(l%2==0) T[l+1]+=val;
			if(r%2==1) T[r-1]+=val;
			l>>=1; r>>=1;
		}
	}
	int query(int pos){
		pos+=nTree;
		int res=0;
		while(pos>0){
			res+=T[pos];
			pos>>=1;
		}
		return res;
	}
};
seg_tree t[MAXN];
bool visited[MAXN][MAXN];
int cost[MAXN][MAXN];
int dp[MAXN],dp_curr[MAXN];
void dp_opt(int l,int r,int optl,int optr){
	if(l>r) return;
	int mid=(l+r)>>1;
	int best=-1,pos=0;
	for(int i=optl;i<=min(mid,optr);++i){
		if(best<(i?dp_curr[i-1]:0)+cost[i][mid]){
			best=(i?dp_curr[i-1]:0)+cost[i][mid];
			pos=i;
		}
	}
	dp[mid]=best;
	dp_opt(l,mid-1,optl,pos);
	dp_opt(mid+1,r,pos,optr);
}
int main()
{
	ios_base::sync_with_stdio(0);
	int r,s; cin>>r>>s;
	for(int i=1;i<=r;++i){
		for(int j=1;j<=s;++j){
			char c; cin>>c;
			if(c=='.') arr[i][j]=-1;
			else arr[i][j]=c-'0';
		}
	}
	vector<pii> shifts={{-1,0},{1,0},{0,-1},{0,1}};
	for(int i=1;i<=r;++i){
		for(int j=1;j<=s;++j){
			if(!visited[i][j]&&arr[i][j]!=-1){
				visited[i][j]=1;
				int L=j,R=j;
				queue<pii> Q;
				Q.push({i,j});
				int total=arr[i][j];
				while(!Q.empty()){
					pii vert=Q.front(); Q.pop();
					for(pii p:shifts){
						int new_x=vert.first+p.first,new_y=vert.second+p.second;
						if(new_x<1||new_x>r||new_y<1||new_y>s||arr[new_x][new_y]==-1||visited[new_x][new_y]) continue;
						total+=arr[new_x][new_y];
						L=min(L,new_y); R=max(R,new_y);
						visited[new_x][new_y]=1;
						Q.push({new_x,new_y});
					}
				}
				for(int k=L;k<=R;++k) t[k].update(1,L,total);
			}
		}
	}
	for(int i=1;i<=s;++i){
		for(int j=i;j<=s;++j){
			cost[i][j]=t[j].query(i);
		}
	}
	for(int i=1;i<=s;++i){
		dp_opt(0,s,0,s);
		int ans=0;
		for(int j=1;j<=s;++j) ans=max(ans,dp[j]);
		for(int j=1;j<=s;++j) dp_curr[j]=dp[j];
		cout<<ans<<"\n";
	}
}

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