Submission #533286

#	Time	Username	Problem	Language	Result	Execution time	Memory
533286		rk42745417	영역 (JOI16_ho_t4)	C++17	38 / 100	945 ms	36012 KiB

2016_ho_t4

#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

signed main() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;

	ll res = 0, prv = 0;
	int x = 0, y = 0;
	set<pair<int, int>> owo;
	auto check = [&](int a, int b) {
		bool ok = 1;
		for(int dx : {0, 1})
			for(int dy : {0, 1})
				ok &= owo.count({a + dx, b + dy});
		return ok;
	};
	owo.insert({x, y});
	const int TIMES = 75;
	for(int ti = 0; ti < min(k, TIMES); ti++) {
		prv = 0;
		for(char c : s) {
			if(c == 'E')
				x++;
			if(c == 'W')
				x--;
			if(c == 'N')
				y++;
			if(c == 'S')
				y--;

			if(owo.count({x, y}))
				continue;
			owo.insert({x, y});

			for(int dx : {0, -1})
				for(int dy : {0, -1})
					prv += check(x + dx, y + dy);
		}
		res += prv;
	}
	res += prv * (k - min(k, TIMES));
	cout << res << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 62