Submission #1000742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000742		Baytoro	Nafta (COI15_nafta)	C++17	100 / 100	478 ms	125008 KiB

nafta

#include <bits/stdc++.h>
//#include "island.h"
#define pb push_back
#define ll long long
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
using namespace std;
#define ll long long
//#ifndef ONLINE_JUDGE
const int N=2005;
int a[N][N],used[N][N];
int sum[N*N],L[N*N],R[N*N];
int r,s;
void dfs(int x, int y, int c){
	if(used[x][y] || a[x][y]==-1 || x<=0 || x>r || y<=0 || y>s) return;
	used[x][y]=c;
	sum[c]+=a[x][y];
	L[c]=min(L[c],y);
	R[c]=max(R[c],y);
	dfs(x-1,y,c);
	dfs(x+1,y,c);
	dfs(x,y-1,c);
	dfs(x,y+1,c);
}
int dp[N][N],cost[N][N];
void rec(int l, int r, int optl, int optr, int k){
	if(l>r) return;
	int md=(l+r)/2;
	int res=0,opt=md;
	for(int i=optl;i<=min(optr,md-1);i++){//<-
		if(dp[i][k-1]+cost[i][md]>res){
			opt=i;
			res=dp[i][k-1]+cost[i][md];
		}
	}
	dp[md][k]=res;
	rec(l,md-1,optl,opt,k);
	rec(md+1,r,opt,optr,k);
}
void solve(){
	cin>>r>>s;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			char c;cin>>c;
			if(c=='.') a[i][j]=-1;
			else a[i][j]=(c-'0');
		}
	}
	
	int cnt=0;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++) 
			if(!used[i][j] && a[i][j]!=-1){ 
				cnt++;L[cnt]=j,R[cnt]=j;
				dfs(i,j,cnt);
			}
	}
	vector<int> col(s+1);
	for(int i=1;i<=s;i++){
		map<int,int> mp;
		for(int j=1;j<=r;j++){
			if(used[j][i] && mp[used[j][i]]==0){
				mp[used[j][i]]=1;
				col[i]+=sum[used[j][i]];
			}
		}
	}
	for(int i=1;i<=s;i++){
		map<int,int> mp;
		vector<pair<int,int> > v;
		int sm=0;
		for(int j=1;j<=r;j++){
			if(used[j][i] && mp[used[j][i]]==0){
				mp[used[j][i]]=1;
				v.pb(make_pair(R[used[j][i]],sum[used[j][i]]));
				sm+=sum[used[j][i]];
			}
		}
		sort(all(v));
		int l=0;
		for(int j=i+1;j<=s;j++){
			while(l<v.size() && j>v[l].fr){
				sm-=v[l].sc;
				l++;
			}
			cost[i][j]=col[j]-sm;
		}
	}
	/*for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++) cout<<cost[i][j]<<' ';
		cout<<endl;
	}
	for(int i=1;i<=s;i++) cout<<col[i]<<' ';
	cout<<endl;*/
	for(int i=1;i<=s;i++)
		dp[i][1]=col[i];
	for(int i=2;i<=s;i++){
		rec(1,s,1,s,i);
	}
	for(int i=1;i<=s;i++){
		int ans=0;
		for(int j=1;j<=s;j++) ans=max(ans,dp[j][i]);
		cout<<ans<<endl;
	}
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
		solve();
	}
}
//#endif

Compilation message (stderr)

nafta.cpp: In function 'void solve()':
nafta.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    while(l<v.size() && j>v[l].fr){
      |          ~^~~~~~~~~

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