QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573926 | #5414. Stop, Yesterday Please No More | PonyHex | WA | 19ms | 8648kb | C++20 | 4.0kb | 2024-09-18 20:19:37 | 2024-09-18 20:19:38 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 2005;
int n, m, k;
string s;
int xl, xr, yl, yr;
vector<pair<int, int> > nums;
int mp[N][N];
void solve() {
cin >> n >> m >> k;
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j <= 2 * m; j++) {
mp[i][j] = 0;
}
}
cin >> s;
int px = 0, py = 0;
int disux = 0, disdx = 0, disly = 0,disry = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'U') {
px--;
}
else if (s[i] == 'D') {
px++;
}
else if (s[i] == 'L') {
py--;
}
else if (s[i] == 'R') {
py++;
}
//判定位置,然后更新dis,然后判定k=n*m,k=0的情况
disux = min(disux, px); disdx = max(disdx, px);
disly = min(disly, py); disry = max(disry, py);
/*
if (disux <= -n || disdx >= n || disly <= -m || disry >= m) {
if (k == 0) {
cout << n * m << endl; return;
}
else if (k == n * m) {
cout << 0 << endl; return;
}
}*/
if (disdx - disux >= n || disry - disly) {
if (k == 0) {
cout << n * m << endl; return;
}
else if (k == n * m) {
cout << 0 << endl; return;
}
}
}
xl = 1 - disux; yl = 1 - disly;
xr = n - disdx; yr = m - disry;
int sum = (yr - yl + 1) * (xr - xl + 1);
int x = 0, y = 0;
nums.push_back({ x,y });
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'U') {
x--;
nums.push_back({ x,y });
}
else if (s[i] == 'D') {
x++;
nums.push_back({ x,y });
}
else if (s[i] == 'L') {
y--;
nums.push_back({ x,y });
}
else if (s[i] == 'R') {
y++;
nums.push_back({ x,y });
}
}
int mix = 1e18, miy = 1e18;
for (auto p = nums.begin(); p != nums.end(); p++) {
mix = min(mix, p->first);
miy = min(miy, p->second);
}
mix--; miy--;
mix = -mix, miy = -miy;
for (auto p = nums.begin(); p != nums.end(); p++) {
mp[p->first + mix][p->second + miy] = 1;
}
for (int i = 1; i <= 2 * n; i++) {
for (int j = 1; j <= 2 * m; j++) {
mp[i][j] = mp[i][j] + mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1];
//cout<<mp[i][j]<<' ';
}//cout<<endl;
}
//cout<<sum<<endl;
int ans = 0;
//枚举起点,1,1一直到n,m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//枚举在原矩阵中起点的位置,获取位置关系
///右下,约束为最大n+mix,m+miy
//左上,如果越界,约束为1,1
int dx = (xl - i), dy = (yl -j);
int x = mix + dx, y = miy + dy;
int xx = mix + dx + (xr - xl), yy = miy + dy + (yr - yl);
if (xx <= 0 || yy <= 0) {
if (0 == sum - k)ans++;
continue;
}
x = max(1ll, x), y = max(1ll, y);
if ((mp[xx][yy] + mp[x - 1][y - 1] - mp[x - 1][yy] - mp[xx][y - 1]) == sum - k)ans++;
// int xx = i, yy = j;
// int x = i - (xr - xl), y = j - (yr - yl);
// x = max(1ll, x); y = max(1ll, y);
//if ((mp[xx][yy] + mp[x - 1][y - 1] - mp[x - 1][yy] - mp[xx][y - 1]) == sum - k)ans++;
//放左上角
}
}
cout << ans << endl;
return;
}
signed main() {
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T_case = 1;
cin >> T_case;
while (T_case--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3700kb
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: 19ms
memory: 8648kb
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 9 3 15 17 240 3 0 0 8 2 18 11 2 0 5 1 0 0 0 0 0 3 0 3 2 0 0 0 9 6 0 320 0 0 0 0 1 4 0 0 0 0 0 0 22 0 51 1 4 6 0 0 48 28 8 3 0 0 0 0 0 1 0 0 44 0 0 2 0 4 30 0 0 105 0 1 17 0 66 0 11 28 0 0 0 0 0 0 90 2 2 0 0 48 0 0 0 0 30 3 0 1 0 0 0 2 0 0 0 0 0 0 20 0 0 0 48 0 0 225 0 1 0 0 11 0 90 0 0 228 ...
result:
wrong answer 3rd numbers differ - expected: '20', found: '1'