QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177385#5414. Stop, Yesterday Please No MoredsakhdkasWA 5ms3676kbC++142.2kb2023-09-12 22:01:542023-09-12 22:01:54

Judging History

你现在查看的是最新测评结果

  • [2023-09-12 22:01:54]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3676kb
  • [2023-09-12 22:01:54]
  • 提交

answer

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

void solve() {
	int n, m, k;
	string s;
	cin >> n >> m >> k >> s;
	int len = s.size();
	int mnx = n, mny = m;
	int mxx = 1, mxy = 1;
	int x = 0, y = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] == 'L') --y;
		if (s[i] == 'R') ++y;
		if (s[i] == 'U') --x;
		if (s[i] == 'D') ++x;
		mnx = min(mnx, n-x);
		mxx = max(mxx, 1-x);
		mny = min(mny, m-y);
		mxy = max(mxy, 1-y);
	}
//	mnx=-mnx;mxx=n-mxx;
//	mny=-mny;mxy=m-mxy;
//	mnx = x-mnx + 1, mxx = x+n - mxx;
//	mny = y-mny + 1, mxy = y+m - mxy;
//	cerr<<mxx<<' '<<mnx<<' '<<mxy<<' '<<mny<<endl;
	if (mnx >= mxx && mny >= mxy) {
		int all = (mny - mxy + 1) * (mnx - mxx + 1);
		int ans = 0;
		vector<vector<int>> a(n + 3, vector<int>(m + 3, 0));
		auto add = [&](int x0, int y0) {
			int sx = mxx + x0;
			int sy = mxy + y0;
			int ex = mnx + x0;
			int ey = mny + y0;
//			cerr<<sx<<' '<<sy<<' '<<ex<<' '<<ey<<endl;
			sx = max(sx, 1); sx = min(sx, n);
			sy = max(sy, 1); sy = min(sy, m);
			ex = max(ex, 1); ex = min(ex, n);
			ey = max(ey, 1); ey = min(ey, m);
			a[sx][sy] += 1;
			a[sx][ey + 1] -= 1;
			a[ex + 1][sy] -= 1;
			a[ex + 1][ey + 1] += 1;
		};
		int x = 0, y = 0;
		vector<pair<int, int>> b;
		for (int i = 0; i < len; i++) {
			if (s[i] == 'L') --y;
			if (s[i] == 'R') ++y;
			if (s[i] == 'U') --x;
			if (s[i] == 'D') ++x;
			b.emplace_back(x, y);
		}
		sort(b.begin(), b.end());
		b.resize(unique(b.begin(), b.end()) - b.begin());
		for (auto [x, y] : b) {
			add(x, y);
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				a[i][j] += a[i - 1][j];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				a[i][j] += a[i][j - 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				int ned = all - k;
				if (i>=mxx&&i<=mnx&&j>=mxy&&j<=mny) ned--;
				int now = a[i][j];
				if (now == ned) {
//					cerr << "ok: " << i << " " << j << endl;
					ans += 1;
				}
			}
		}
		cout << ans << "\n";
	} else {
		if (k == 0) {
			cout << n * m << "\n";
		} else {
			cout << 0 << "\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	 
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3476kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 3676kb

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
19
0
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
1
2
3
7
0
29
14
21
0
8
1
9
13
5
320
3
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
5
6
3
11
48
28
8
7
22
49
13
10
2
0
4
18
44
0
14
9
0
4
30
14
99
105
5
14
17
0
66
10
11
28
52
34
8
33
14
0
90
0
0
11
3
48
30
36
12
0
30
7
8
3
11
16
45
20
34
0
20
0
21
0
...

result:

wrong answer 3rd numbers differ - expected: '20', found: '19'