Submission #121604

#	Time	Username	Problem	Language	Result	Execution time	Memory
121604		MetB	Nafta (COI15_nafta)	C++14	100 / 100	478 ms	191768 KiB

nafta

#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
 
typedef long long ll;
typedef long double ld;
 
const ll MOD = 2004, INF = 1e18 + 1;
 
using namespace std;

int C[2002][2002], d[2002][2002];

int r, s, u[2002][2002];

char a[2002][2002];

struct BIT
{
	int t[10000];

	void update (int x, int d)
	{
		for (; x <= s; x = (x | (x + 1)))
			t[x] += d;
	}

	int get (int r)
	{
		int sum = 0;

		for (;r >= 0; r = (r & (r + 1)) - 1)
			sum += t[r];
		return sum;
	}

	int get (int l, int r)
	{
		return get (r) - get (l - 1);
	}
} t;

struct pool
{
	int l, r, sum;

	void merge (const pool& b)
	{
		sum += b.sum;
		l = min (l, b.l);
		r = max (r, b.r);
	}

	bool operator< (const pool& b) const
	{
		return r < b.r;
	}
};

vector <pool> v;

pool dfs (int x, int y)
{
	u[x][y] = 1;
	pool ans = {y, y, a[x][y] - '0'};

	if (x && a[x-1][y] != '.' && !u[x-1][y]) ans.merge (dfs (x - 1, y));
	if (y && a[x][y-1] != '.' && !u[x][y-1]) ans.merge (dfs (x, y - 1));
	if (x < r - 1 && a[x+1][y] != '.' && !u[x+1][y]) ans.merge (dfs (x + 1, y));
	if (y < s - 1 && a[x][y+1] != '.' && !u[x][y+1]) ans.merge (dfs (x, y + 1));

	return ans;
}

int calc (int i, int k, int j)
{
	return C[k][j] + d[i-1][k-1];
}

void Rec (int k, int l, int r, int optl, int optr)
{
	if (l > r) return;

	int m = (l + r) / 2;

	int mn = optl;

	for (int i = optl; i <= min (m, optr); i++)
		if (calc (k, mn, m) < calc (k, i, m)) mn = i;

	d[k][m] = calc (k, mn, m);

	Rec (k, l, m - 1, optl, mn);
	Rec (k, m + 1, r, mn, optr);

}

int main ()
{
	cin >> r >> s;

	for (int i = 0; i < r; i++)
		scanf ("%s", a[i]);

	for (int i = 0; i < r; i++)
		for (int j = 0; j < s; j++)
			if (!u[i][j] && a[i][j] != '.') v.push_back (dfs (i, j));

	int ptr = 0;

	sort (v.begin(), v.end());

	for (int i = 0; i < s; i++)
	{
		while (ptr < v.size () && v[ptr].r <= i)
		{
			t.update (v[ptr].l, v[ptr].sum);
			t.update (v[ptr].r + 1, -v[ptr].sum);
			ptr++;
		}

		for (int j = 0; j <= i; j++)
		{
			C[j][i] = t.get (0, j);
			d[0][i] = max (d[0][i], C[j][i]);
		}
	}


	for (int i = 1; i < s; i++)
		Rec (i, 0, s - 1, 0, s - 1);

	for (int i = 0; i < s; i++)
		printf ("%d\n", d[i][s-1]);
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:124:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < v.size () && v[ptr].r <= i)
          ~~~~^~~~~~~~~~~
nafta.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s", a[i]);
   ~~~~~~^~~~~~~~~~~~

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