oj.uz

Submission #121604

# Submission time Handle Problem Language Result Execution time Memory
121604 2019-06-26T20:28:34 Z MetB Nafta (COI15_nafta) C++14
100 / 100
 478 ms 191768 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 4 ms 1124 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 4 ms 1124 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 10 ms 5824 KB Output is correct
8 Correct 10 ms 5760 KB Output is correct
9 Correct 12 ms 8832 KB Output is correct
10 Correct 9 ms 4864 KB Output is correct
11 Correct 9 ms 4864 KB Output is correct
12 Correct 8 ms 4736 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 4 ms 1124 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 10 ms 5824 KB Output is correct
8 Correct 10 ms 5760 KB Output is correct
9 Correct 12 ms 8832 KB Output is correct
10 Correct 9 ms 4864 KB Output is correct
11 Correct 9 ms 4864 KB Output is correct
12 Correct 8 ms 4736 KB Output is correct
13 Correct 330 ms 59644 KB Output is correct
14 Correct 327 ms 56664 KB Output is correct
15 Correct 478 ms 191768 KB Output is correct
16 Correct 270 ms 52692 KB Output is correct
17 Correct 314 ms 49848 KB Output is correct
18 Correct 299 ms 49820 KB Output is correct