QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177385 | #5414. Stop, Yesterday Please No More | dsakhdkas | WA | 5ms | 3676kb | C++14 | 2.2kb | 2023-09-12 22:01:54 | 2023-09-12 22:01:54 |
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 = 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;
}
详细
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'