QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22575 | #2841. 赛艇 | blackswallow# | TL | 7220ms | 213068kb | C++20 | 3.3kb | 2022-03-09 21:23:51 | 2022-04-30 01:22:42 |
Judging History
answer
//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1
const int MAXN = 1510;
const int MAXK = 5e6 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, k, Ans;
int sL[MAXN], sR[MAXN], sum[MAXN][MAXN];
bitset<MAXN> P[MAXN][MAXN], V[MAXN];
char mmp[MAXN][MAXN], mv[MAXK];
bool tmp[MAXN << 1][MAXN << 1];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }
int S(int a, int b, int c, int d) {
return sum[b][d] - sum[a - 1][d] - sum[b][c - 1] + sum[a - 1][c - 1];
}
signed main () {
#ifdef FILE
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif
read(n), read(m), read(k);
for(int i = 1; i <= n; ++i) {
scanf("%s", mmp[i] + 1);
for(int j = 1; j <= m; ++j) {
if(mmp[i][j] == '0') P[i][0].set(j);
sum[i][j] = mmp[i][j] - '0';
}
for(int j = 1; j <= m; ++j)
P[i][j] = P[i][j - 1] >> 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
scanf("%s", mv + 1);
int curx = n, cury = m;
tmp[curx][cury] = true;
for(int i = 1; i <= k; ++i) {
if(mv[i] == 'w') curx--;
if(mv[i] == 'a') cury--;
if(mv[i] == 's') curx++;
if(mv[i] == 'd') cury++;
tmp[curx][cury] = true;
}
int H = 0, mn = INF, len = 0;
for(int i = 0, sum; i < (MAXN << 1); ++i) {
sum = 0;
for(int j = 0; j < (MAXN << 1); ++j)
sum += tmp[i][j];
if(!sum) continue;
++H; sL[H] = -1;
for(int j = 0; j < (MAXN << 1); ++j) {
if(!tmp[i][j]) continue;
if(sL[H] == -1) sL[H] = j;
sR[H] = j;
}
}
for(int i = 1; i <= H; ++i) mn = min(mn, sL[i]);
for(int i = 1; i <= H; ++i) {
sL[i] -= mn, sR[i] -= mn;
len = max(len, sR[i] + 1);
}
for(int i = 0, t = 0, cc = 0; i < (MAXN << 1); ++i) {
t = 0;
for(int j = 0; j < (MAXN << 1); ++j) t += tmp[i][j];
if(!t) continue;
++cc;
for(int j = 0; j < (MAXN << 1); ++j) {
if(!tmp[i][j]) continue;
V[cc].set(j - mn);
}
}
/*for(int i = 1; i <= H; ++i) {
for(int j = 0; j < len; ++j)
cout << V[i][j];
cout << endl;
}*/
for(int i = 1; i + H - 1 <= n; ++i) {
for(int j = 1; j + len - 1 <= m; ++j) {
bool flag = true;
if(S(i, i + H - 1, j, j + len - 1) == 0) {
++Ans;
continue;
}
for(int d = 1; d <= H; ++d) {
if((P[i + d - 1][j] & V[d]) != V[d]) {
flag = false;
break;
}
}
Ans += flag;
}
}
printf("%d\n", Ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14020kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 50ms
memory: 68712kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77549
result:
ok single line: '77549'
Test #3:
score: 0
Accepted
time: 364ms
memory: 70244kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #4:
score: 0
Accepted
time: 214ms
memory: 69196kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #5:
score: 0
Accepted
time: 331ms
memory: 69676kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #6:
score: 0
Accepted
time: 185ms
memory: 68844kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #7:
score: 0
Accepted
time: 4030ms
memory: 212412kb
input:
1000 1000 300000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
83496
result:
ok single line: '83496'
Test #8:
score: 0
Accepted
time: 3841ms
memory: 213068kb
input:
1000 1000 1000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
63001
result:
ok single line: '63001'
Test #9:
score: 0
Accepted
time: 7220ms
memory: 212504kb
input:
1000 1000 1500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
62500
result:
ok single line: '62500'
Test #10:
score: -100
Time Limit Exceeded
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...