QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491377 | #5414. Stop, Yesterday Please No More | 333zhan | WA | 4ms | 3784kb | C++20 | 2.5kb | 2024-07-25 19:08:37 | 2024-07-25 19:08:37 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read () {
int w = 1, s = 0; char ch = getchar ();
for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
return s * w;
}
void solve () {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
int u = 1, d = n, l = 1, r = m;
int uu = 1, dd = n, ll = 1, rr = m;
for (auto c : s) {
if (c == 'U') {
uu ++; dd ++;
} else if (c == 'D') {
uu --; dd --;
} else if (c == 'L') {
ll ++; rr ++;
} else {
ll --; rr --;
}
u = max (uu, u);
d = min (d, dd);
l = max (ll, l);
r = min (rr, r);
}
// cerr << u << " " << d << " " << l << " " << r << '\n';
if (u > d || l > r) {
if (k == 0) {
cout << n * m << '\n';
} else {
cout << 0 << '\n';
}
return;
}
if (k > (d - u + 1) * (r - l + 1)) {
cout << 0 << '\n';
return;
}
vector pre (n * 2 + 10, vector <int> (m * 2 + 10));
int x = n + 1, y = m + 1;
pre[x][y] = 1;
for (auto c : s) {
if (c == 'U') {
x --;
} else if (c == 'D') {
x ++;
} else if (c == 'L') {
y --;
} else {
y ++;
}
pre[x][y] = 1;
}
for (int i = 1; i <= 2 * n; i ++) {
for (int j = 1; j <= 2 * m; j ++) {
pre[i][j] += pre[i][j - 1];
}
}
for (int i = 1; i <= 2 * n; i ++) {
for (int j = 1; j <= 2 * m; j ++) {
pre[i][j] += pre[i - 1][j];
}
}
auto work = [&] (int x, int y) {
int x1 = u + x, x2 = d + x;
int y1 = l + y, y2 = r + y;
return pre[x2][y2] - pre[x2][y1 - 1] - pre[x1 - 1][y2] + pre[x1 - 1][y1 - 1];
};
int ans = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
x = n + 1 - i;
y = m + 1 - j;
int sum = work (x, y);
if (sum == (d - u + 1) * (r - l + 1) - k) {
ans ++;
}
}
}
cout << ans << '\n';
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
int T = 1;
cin >> T;
// T = read ();
while (T --) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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: 4ms
memory: 3784kb
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 1 99 5 15 16 240 6 0 0 1 11 18 13 0 12 16 108 4 1 1 3 48 1 1 3 4 0 7 10 9 4 5 320 8 5 3 0 0 3 0 11 0 0 6 0 22 36 51 12 5 6 1 2 48 28 8 63 11 49 13 4 2 108 7 9 44 0 1 8 0 4 30 12 99 105 5 1 17 0 66 8 11 28 52 15 56 11 5 56 90 14 0 121 3 48 1 16 10 0 30 1 3 3 7 16 45 9 32 0 19 0 4 0 39 0 20 12 ...
result:
wrong answer 3rd numbers differ - expected: '20', found: '1'