Submission #363543

#	Time	Username	Problem	Language	Result	Execution time	Memory
363543		arnold518	Nafta (COI15_nafta)	C++14	34 / 100	1085 ms	28816 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 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;
			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++)
	{
		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 'int main()':
nafta.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
nafta.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%s", S[i]+1);
      |                          ~~~~~^~~~~~~~~~~~~~

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