oj.uz

Submission #341300

# Submission time Handle Problem Language Result Execution time Memory
341300 2020-12-29T11:38:31 Z ogibogi2004 Nafta (COI15_nafta) C++14
100 / 100
 918 ms 120960 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2048;
const int INF=1e9;
int pref[MAXN][MAXN];
int n,m,val,maxy;
char c[MAXN][MAXN];
int dp[MAXN][MAXN];
int opt[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int maxdp;
void dfs(int x,int y)
{
	vis[x][y]=1;
	maxy=max(maxy,y);
	val+=c[x][y]-'0';
	for(int l=0;l<4;++l)
	{
		int x1=x+dx[l];
		int y1=y+dy[l];
		if(x1<1||y1<1||x1>n||y1>m)continue;
		if(c[x1][y1]=='.')continue;
		if(vis[x1][y1])continue;
		dfs(x1,y1);
	}
}
int get_sum(int l1,int l2,int r1,int r2)
{
	return pref[l2][r2]-pref[l1-1][r2]-pref[l2][r1-1]+pref[l1-1][r1-1];
}
void calc(int d,int idx,int optl,int optr)
{
	for(int i=optl;i<=optr&&i<idx;++i)
	{
		int s=get_sum(i+1,idx,idx,m);
		if(dp[i][d-1]+s>dp[idx][d])
		{
			dp[idx][d]=dp[i][d-1]+s;
			opt[idx][d]=i;
		}
	}
	maxdp=max(maxdp,dp[idx][d]);
}
void solve(int d,int l,int r,int optl,int optr)
{
	if(l>r)return;
	int mid=(l+r)/2;
	//cout<<mid<<" "<<optl<<" "<<optr<<endl;
	calc(d,mid,optl,optr);
	if(l==r)return;
	solve(d,mid+1,r,opt[mid][d],optr);
	solve(d,l,mid-1,optl,opt[mid][d]);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin>>c[i][j];
		}
	}
	//cout<<"*\n";
	for(int j=1;j<=m;++j)
	{
		for(int i=1;i<=n;++i)
		{
			if(vis[i][j])continue;
			if(c[i][j]=='.')continue;
			val=0;maxy=0;
			dfs(i,j);
			pref[j][maxy]+=val;
		}
	}
	//cout<<"*\n";
	for(int i1=1;i1<=m;++i1)
	{
		for(int i2=1;i2<=m;++i2)
		{
			pref[i1][i2]=pref[i1][i2]+pref[i1-1][i2]+pref[i1][i2-1]-pref[i1-1][i2-1];
		}
	}
	for(int i=0;i<=m;++i)
	{
		for(int j=0;j<=m;++j)
		{
			dp[i][j]=-INF;
		}
	}
	dp[0][0]=0;
	for(int k=1;k<=m;++k)
	{
		maxdp=0;
		solve(k,1,m,0,m);
		cout<<maxdp<<'\n';
	}
return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 11 ms 5260 KB Output is correct
8 Correct 12 ms 5228 KB Output is correct
9 Correct 13 ms 6508 KB Output is correct
10 Correct 11 ms 5228 KB Output is correct
11 Correct 12 ms 5228 KB Output is correct
12 Correct 13 ms 5228 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 11 ms 5260 KB Output is correct
8 Correct 12 ms 5228 KB Output is correct
9 Correct 13 ms 6508 KB Output is correct
10 Correct 11 ms 5228 KB Output is correct
11 Correct 12 ms 5228 KB Output is correct
12 Correct 13 ms 5228 KB Output is correct
13 Correct 857 ms 56556 KB Output is correct
14 Correct 910 ms 60524 KB Output is correct
15 Correct 901 ms 120960 KB Output is correct
16 Correct 832 ms 60396 KB Output is correct
17 Correct 918 ms 60736 KB Output is correct
18 Correct 882 ms 60396 KB Output is correct