QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#154353 | #7120. Soccer | skip2004# | 30 | 8ms | 36444kb | C++17 | 2.4kb | 2023-08-31 16:52:55 | 2023-08-31 16:52:56 |
Judging History
answer
#include "soccer.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 2005;
int up[N][N], down[N][N];
void clear(int x) {
for(int i = 0;i < N;++i)
for(int j = 0;j < N;++j) {
up[i][j] = 0;
down[i][j] = 0;
}
}
int dp[N][N];
struct rmq {
std::vector<int> st[12];
rmq(const std::vector<int> & v) {
st[0] = v;
for(int i = 1;(1 << i) - 1 < (int) v.size();++i) {
st[i].resize(v.size() - (1 << i));
for(int j = 0;j + (1 << i) - 1 < (int) v.size();++j) {
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
int qry(int l, int r) {
const int lg = std::__lg(r - l + 1);
return std::min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
};
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
for(int i = 0;i < N;++i) {
for(int j = 0;j < N;++j) {
if(F[i][j]) {
up[i][j] = 0;
} else {
up[i][j] = 1;
if(i) up[i][j] += up[i - 1][j];
}
}
}
for(int i = N - 1;i >= 0;--i) {
for(int j = 0;j < N;++j) {
if(F[i][j]) {
down[i][j] = 0;
} else {
down[i][j] = 1 + down[i + 1][j];
}
}
}
int ans = 0;
for(int i = 0;i < N;++i) {
std::vector<int> a(up[i], up[i] + N);
std::vector<int> b(down[i], down[i] + N);
rmq A(a), B(b);
auto qry = [&](int l, int r) {
return A.qry(l, r) + B.qry(l, r) - 1;
int x = *min_element(a.begin() + l, a.begin() + r + 1);
int y = *min_element(b.begin() + l, b.begin() + r + 1);
return x + y - 1;
};
for(int x = 0;x < N;++x) {
for(int y = x;y < N;++y) {
dp[x][y] = -1e9;
}
for(int y = x;y < N;++y) {
if(!a[y] || !b[y]) break;
dp[x][y] = 0;
}
}
for(int x = 0;x < N;++x) {
for(int y = N - 1;y >= x;--y) {
dp[x][y] += qry(x, y);
dp[x + 1][y] = std::max(dp[x + 1][y], dp[x][y]);
dp[x][y - 1] = std::max(dp[x][y - 1], dp[x][y]);
if(x == y) ans = std::max(ans, dp[x][y]);
}
}
}
clear(N);
return ans;
}
#ifdef zqj
int main() {
freopen("1.in", "r", stdin);
int N;
assert(1 == scanf("%d", &N));
std::vector<std::vector<int>> F(N, std::vector<int>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
assert(1 == scanf("%d", &F[i][j]));
}
}
fclose(stdin);
int res = biggest_stadium(N, F);
printf("%d\n", res);
fclose(stdout);
return 0;
}
#endif
詳細信息
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 6
Accepted
time: 1ms
memory: 34540kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 1ms
memory: 34596kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #3:
score: 0
Dangerous Syscalls
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
result:
Subtask #2:
score: 8
Accepted
Test #10:
score: 8
Accepted
time: 8ms
memory: 34536kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #11:
score: 8
Accepted
time: 4ms
memory: 34616kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #12:
score: 8
Accepted
time: 0ms
memory: 35484kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #13:
score: 8
Accepted
time: 1ms
memory: 34540kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 0 1 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
ok ok
Test #14:
score: 8
Accepted
time: 1ms
memory: 35000kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Test #15:
score: 8
Accepted
time: 8ms
memory: 34532kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 1 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 7
result:
ok ok
Test #16:
score: 8
Accepted
time: 1ms
memory: 34560kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9
result:
ok ok
Test #17:
score: 8
Accepted
time: 1ms
memory: 34760kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 1 0 0 0 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Test #18:
score: 8
Accepted
time: 0ms
memory: 34596kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 1 1 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 2
result:
ok ok
Test #19:
score: 8
Accepted
time: 3ms
memory: 34532kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 1 0 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3
result:
ok ok
Test #20:
score: 8
Accepted
time: 1ms
memory: 34828kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Subtask #3:
score: 22
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 22
Accepted
time: 1ms
memory: 34780kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 43
result:
ok ok
Test #22:
score: 22
Accepted
time: 4ms
memory: 34728kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 35
result:
ok ok
Test #23:
score: 22
Accepted
time: 5ms
memory: 34728kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 18
result:
ok ok
Test #24:
score: 22
Accepted
time: 4ms
memory: 34544kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 8
result:
ok ok
Test #25:
score: 22
Accepted
time: 3ms
memory: 35188kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9
result:
ok ok
Test #26:
score: 22
Accepted
time: 1ms
memory: 34756kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Test #27:
score: 22
Accepted
time: 1ms
memory: 35104kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 12
result:
ok ok
Test #28:
score: 22
Accepted
time: 2ms
memory: 35288kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 13
result:
ok ok
Test #29:
score: 22
Accepted
time: 4ms
memory: 34776kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 12
result:
ok ok
Test #30:
score: 22
Accepted
time: 1ms
memory: 35544kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 10
result:
ok ok
Test #31:
score: 22
Accepted
time: 2ms
memory: 36444kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 20
result:
ok ok
Test #32:
score: 22
Accepted
time: 1ms
memory: 34612kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 21
result:
ok ok
Subtask #4:
score: 0
Dangerous Syscalls
Dependency #3:
100%
Accepted
Test #33:
score: 18
Accepted
time: 1ms
memory: 35308kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 24
result:
ok ok
Test #34:
score: 0
Dangerous Syscalls
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 ...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%