QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176440 | #5414. Stop, Yesterday Please No More | Zhou_JK | WA | 60ms | 4024kb | C++23 | 2.1kb | 2023-09-11 17:12:15 | 2023-09-11 17:12:15 |
Judging History
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 = 0, mny = 0;
int mxx = 0, mxy = 0;
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, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
}
mnx = x-mnx + 1, mxx = x+n - mxx;
mny = y-mny + 1, mxy = y+m - mxy;
if (mnx <= mxx && mny <= mxy) {
int all = (mxy - mny + 1) * (mxx - mnx + 1);
int ans = 0;
vector<vector<int>> a(n + 3, vector<int>(m + 3, 0));
auto add = [&](int x0, int y0) {
int sx = mnx - x0;
int sy = mny - y0;
int ex = mxx - x0;
int ey = mxy - y0;
sx = max(sx, 0); sx = min(sx, n + 1);
sy = max(sy, 0); sy = min(sy, m + 1);
ex = max(ex, 0); ex = min(ex, n + 1);
ey = max(ey, 0); ey = min(ey, m + 1);
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 = 0; j <= m; j++)
a[i][j] += a[i - 1][j];
for (int i = 0; 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;
int now = a[i][j];
if (mnx <= i && i <= mxx && mny <= j && j <= mxy) {
now += 1;
}
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: 0ms
memory: 3868kb
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: 60ms
memory: 4024kb
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 2 0 8 15 34 240 9 0 0 3 12 18 26 16 12 19 108 8 0 2 3 14 0 15 14 5 0 8 1 9 5 5 320 1 5 3 0 0 12 0 11 0 0 12 0 22 36 51 23 1 6 0 11 48 28 8 7 22 49 13 10 2 0 4 18 44 0 0 9 0 4 30 14 99 105 5 14 17 0 66 10 11 28 52 32 8 22 14 0 90 0 0 11 3 48 29 36 8 0 30 4 8 3 11 16 45 20 18 0 20 0 19 0 9 0 20...
result:
wrong answer 3rd numbers differ - expected: '20', found: '2'