QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176385 | #5414. Stop, Yesterday Please No More | ucup-team1321 | RE | 0ms | 3628kb | C++20 | 1.9kb | 2023-09-11 16:27:27 | 2023-09-11 16:27:28 |
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 + 2, vector<int>(m + 2, 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, 1);
sy = max(sy, 1);
ex = min(ex, n);
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;
b.emplace_back(0, 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;
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++) {
if (k + a[i][j] == all) {
// 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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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
Runtime Error
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...