Submission #363545

#	Time	Username	Problem	Language	Result	Execution time	Memory
363545		arnold518	Nafta (COI15_nafta)	C++14	100 / 100	541 ms	47120 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};

int N, M;
char S[MAXN+10][MAXN+10];

struct Data
{
	int l, r, v;
};
vector<Data> V;
vector<pii> V2[MAXN+10];

int dp[MAXN+10][MAXN+10];
int f[MAXN+10][MAXN+10];

void solve(int l1, int r1, int l2, int r2, int k)
{
	if(l2>r2) return;
	int mid1=l1, mid2=l2+r2>>1;
	int val=-1;
	for(int i=l1; i<mid2 && i<=r1; i++)
	{
		int t=dp[i][k-1]+f[i][mid2];
		if(val<t)
		{
			val=t;
			mid1=i;
		}
	}
	dp[mid2][k]=val;
	solve(l1, mid1, l2, mid2-1, k);
	solve(mid1, r1, mid2+1, r2, k);
}	

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf("%s", S[i]+1);

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(S[i][j]=='.') continue;

			int sum=0, l=j, r=j;
			queue<pii> Q;
			Q.push({i, j});
			sum+=S[i][j]-'0';
			S[i][j]='.';

			while(!Q.empty())
			{
				pii now=Q.front(); Q.pop();
				for(int i=0; i<4; i++)
				{
					int ny=now.first+dy[i], nx=now.second+dx[i];
					if(!(1<=ny && ny<=N && 1<=nx && nx<=M)) continue;
					if(S[ny][nx]=='.') continue;
					Q.push({ny, nx});
					l=min(l, nx);
					r=max(r, nx);
					sum+=S[ny][nx]-'0';
					S[ny][nx]='.';
				}
			}
			V.push_back({l, r, sum});
			V2[l].push_back({r, sum});
		}
	}

	for(int i=1; i<=M; i++)
	{
		V2[i].push_back({M+1, 0});
		sort(V2[i].begin(), V2[i].end());
		for(int j=V2[i].size()-2; j>=0; j--)
		{
			V2[i][j].second+=V2[i][j+1].second;
		}
	}

	for(int i=1; i<=M; i++)
	{
		int val=0;
		for(int j=i-1; j>=0; j--)
		{
			val+=lower_bound(V2[j+1].begin(), V2[j+1].end(), pii(i, 0))->second;
			f[j][i]=val;
		}
	}
	for(int i=1; i<=M; i++)
	{
		solve(0, N, 1, N, i);
	}
/*
	for(int i=1; i<=M; i++)
	{
		int val=0;
		for(int j=i-1; j>=0; j--)
		{
			val+=lower_bound(V2[j+1].begin(), V2[j+1].end(), pii(i, 0))->second;
			for(int k=1; k<=M; k++)
			{
				dp[i][k]=max(dp[i][k], dp[j][k-1]+val);
			}
		}
	}
*/
	/*
	for(int i=1; i<=M; i++)
	{
		for(int j=1; j<=M; j++)
		{
			printf("%d ", dp[i][j]);
		}
		printf("\n");
	}
	*/
	for(int i=1; i<=M; i++)
	{
		int ans=0;
		for(int j=1; j<=M; j++)
		{
			ans=max(ans, dp[j][i]);
		}
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:29:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int mid1=l1, mid2=l2+r2>>1;
      |                    ~~^~~
nafta.cpp: In function 'int main()':
nafta.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
nafta.cpp:48:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  for(int i=1; i<=N; i++) scanf("%s", S[i]+1);
      |                          ~~~~~^~~~~~~~~~~~~~

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