QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163896 | #7120. Soccer | zhouhuanyi | 0 | 279ms | 168640kb | C++14 | 1.2kb | 2023-09-04 16:18:36 | 2023-09-04 16:18:37 |
Judging History
answer
#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 3000
using namespace std;
const int inf=(int)(1e9);
int n,ans,R[N+1][N+1],dp[N+1][N+1],ls[N+1],rs[N+1],fa[N+1][N+1],l[N+1][N+1],r[N+1][N+1],dque[N+1],top;
bool used[N+1][N+1];
int calc(int x,int y)
{
if (R[x][y]==y-1) return -inf;
if (used[x][y]) return dp[x][y];
int res=r[y][x]-l[y][x]+1;
if (y+1<=n) res=max(res,calc(x,y+1)+r[y][x]-l[y][x]+1);
if (fa[y][x]) res=max(res,calc(fa[y][x],y));
used[x][y]=1,dp[x][y]=res;
return res;
}
int biggest_stadium(int SN,vector<vector<int>>F)
{
n=SN;
for (int i=1;i<=n;++i) R[i][n+1]=n;
for (int i=1;i<=n;++i)
for (int j=n;j>=1;--j)
{
if (!F[i-1][j-1]) R[i][j]=R[i][j+1];
else R[i][j]=j-1;
}
for (int i=1;i<=n;++i)
{
top=0;
for (int j=1;j<=n;++j) ls[j]=rs[j]=0;
for (int j=1;j<=n;++j)
{
while (top&&R[dque[top]][i]>=R[j][i]) ls[j]=dque[top],top--;
if (top) rs[dque[top]]=j;
l[i][j]=dque[top]+1,dque[++top]=j;
}
for (int j=n;j>=1;--j)
{
if (ls[j]) fa[i][ls[j]]=j;
if (rs[j]) fa[i][rs[j]]=j;
if (rs[j]) r[i][j]=r[i][rs[j]];
else r[i][j]=j;
}
}
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
ans=max(ans,calc(i,j));
return ans;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 3ms
memory: 9960kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 2ms
memory: 12308kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #3:
score: 1.5
Acceptable Answer
time: 1ms
memory: 16912kb
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:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9700
result:
points 0.250 partial
Test #4:
score: 6
Accepted
time: 17ms
memory: 44108kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 500 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:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 236536
result:
ok ok
Test #5:
score: 6
Accepted
time: 279ms
memory: 168640kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 2000 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:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3786181
result:
ok ok
Test #6:
score: 6
Accepted
time: 2ms
memory: 12064kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 9 1 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:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 80
result:
ok ok
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 12360kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 10 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 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:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 90
result:
wrong answer wrong
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 2
Acceptable Answer
time: 2ms
memory: 11988kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
points 0.250 partial
Test #11:
score: 2
Acceptable Answer
time: 2ms
memory: 12028kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3
result:
points 0.250 partial
Test #12:
score: 2
Acceptable Answer
time: 2ms
memory: 12060kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
points 0.250 partial
Test #13:
score: 8
Accepted
time: 0ms
memory: 14060kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 0 1 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
ok ok
Test #14:
score: 2
Acceptable Answer
time: 0ms
memory: 12104kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
points 0.250 partial
Test #15:
score: 0
Wrong Answer
time: 2ms
memory: 12040kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 1 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
wrong answer wrong
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%