Submission #96831

#	Time	Username	Problem	Language	Result	Execution time	Memory
96831		diamond_duke	조개 줍기 (KOI17_shell)	C++11	100 / 100	1072 ms	48504 KiB

shell

#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
int n;
struct BIT
{
	int seg[2005];
	BIT() { memset(seg, 0, sizeof(seg)); }
	inline void modify(int pos, int x)
	{
		for (; pos <= n; pos += pos & -pos)
			seg[pos] += x;
	}
	inline int query(int pos)
	{
		int res = 0;
		for (; pos; pos -= pos & -pos)
			res += seg[pos];
		return res;
	}
} seg[2005];
int dp[2005][2005], arr[2005][2005], st[2005], en[2005];
inline int query(int x, int y) { return dp[x][y] + seg[x].query(y); }
int main()
{
	// freopen("KOI2017-T4.in", "r", stdin);
	scanf("%d", &n);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", arr[i] + j);
			dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
			ans += dp[i][j];
		}
	}
	printf("%lld\n", ans);
	for (int t = 0; t < n; t++)
	{
		char tp;
		int xx, yy;
		scanf(" %c%d%d", &tp, &xx, &yy);
		int x = xx, y = yy, d = tp == 'U' ? 1 : -1;
		memset(st, 0x3f, sizeof(st));
		memset(en, 0, sizeof(en));
		st[x] = en[x] = y;
		while (x <= n)
		{
			if (y < n && std::max(query(x - 1, y + 1), query(x, y)) + d ==
					std::max(query(x - 1, y + 1), query(x, y) + d))
				y++;
			else
				x++;
			en[x] = std::max(en[x], y);
		}
		x = xx;
		y = yy;
		while (y <= n)
		{
			if (x < n && std::max(query(x + 1, y - 1), query(x, y)) + d ==
					std::max(query(x + 1, y - 1), query(x, y) + d))
				x++;
			else
				y++;
			if (en[x] < y)
				break;
			st[x] = std::min(st[x], y);
		}
		for (int i = xx; i <= n; i++)
		{
			if (st[i] > en[i])
				continue;
			ans += (en[i] - st[i] + 1) * d;
			seg[i].modify(st[i], d);
			seg[i].modify(en[i] + 1, -d);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shell.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", arr[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~
shell.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d", &tp, &xx, &yy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 34 / 34
• Subtask 3: 54 / 54