Submission #95614

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

shell

#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
int dp[2005][2005], arr[2005][2005], st[2005], en[2005], 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];
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 cas = 0; cas < n; cas++)
	{
		memset(st, 0x3f, sizeof(st));
		memset(en, 0, sizeof(en));
		char tp;
		int sx, sy;
		scanf(" %c%d%d", &tp, &sx, &sy);
		int val = tp == 'U' ? 1 : -1, x = sx, y = sy;
		st[x] = en[x] = y;
		while (true)
		{
			if (y < n && std::max(query(x - 1, y + 1), query(x, y)) + val ==
					std::max(query(x - 1, y + 1), query(x, y) + val))
				y++;
			else
				x++;
			if (x > n)
				break;
			en[x] = y;
		}
		x = sx;
		y = sy;
		while (true)
		{
			if (x < n && std::max(query(x + 1, y - 1), query(x, y)) + val ==
					std::max(query(x + 1, y - 1), query(x, y) + val))
				x++;
			else
				y++;
			if (y > n || en[x] < y)
				break;
			st[x] = std::min(st[x], y);
		}
		for (int i = sx; i <= n; i++)
		{
			if (st[i] > en[i])
				continue;
			ans += (en[i] - st[i] + 1) * val;
			seg[i].modify(st[i], val);
			seg[i].modify(en[i] + 1, -val);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shell.cpp:33: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:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d", &tp, &sx, &sy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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